题面 P4297 [NOI2006]网络收费 Solution 这题喵啊。 首先，我们会发现统计两个点互相的贡献是一个极其困难的问题。 但是，仔细观察那张收费表格后会发现，我们可以重新定义一下这个收费：我们假设路由器节点的颜色为叶子中数目较多的颜色，当一个叶子结点颜色与路由器节点颜色相同的时候不收钱，否则收一份钱。我们可以惊讶的发现，这样做之后我们的新收费做法就与原来题目要求的重合了，而且...

题面 SDOI2009 学校食堂 Solution 这是一道状压妙题。 首先，因为后面的东西能提到前面来做，导致了严重的后效性。为了消除这个后效性，考虑用状压来处理这个问题。 我们可以发现最多的提前量很小，只有7，考虑这样设： 设$f[i][j][k]$表示$[1,i-1]$已经完成了，从$i$开始往后7个的完成状态为$j$，上一个完成的相对$i-1$的位置为k。 转移比较正常：我们枚举一...

题面：洛谷 Solution 首先，我们可以先康一康题目的数据范围：n<=18，应该是状压或者是搜索。 事实上，这题搜索和状压DP都是能做的。 （因为搜索在我心中留下了阴影（斗地主），所以在这里，我讲状压DP的做法） 根据我们以往设计状压DP的经验，我们可以很轻松地设计这一题的状态： 设f[i]表示打下的猪猪的状态为i的方案数，（状态在这里用二进制方式来表示，例如：00101表示打下...

题面 传送门：洛谷 Solution 这道题的是一道很巧妙的状压DP题。 首先，看到数据范围，应该状压DP没错了。 根据我们之前状压方程的设计经验，我们很快就能设计出这样的方程： 设$f[i][j]$表示用到第i个元素，当前连接状态为j的开销的min 但是我们很快就会发现，这个方程没法转移，因为随着连接方案的不同，新插入的点的K值会不同。 怎么办呢？ 这时候我们可以重新设计一个巧妙的的状态...