题目： P2704 [NOI2001]炮兵阵地 解析： 和互不侵犯一样 就是多了一格 用\(f[i][j][k]\)表示第i行，上一行状态为\(j\)，上上行状态为\(k\)的最多的可以放的炮兵 发现\(100\times 1024\times 1024\)开不下 还是通过简单的搜索发现就算\(m==10\)时合法的状态只有\(60\)种 \(100\times 60\times 60\)就没问题了 然后就和互不侵犯一样，枚举状态就可以了 状态转移 \(f[i][j][k] = max\{f[i][j][k], f[i-1][k][l]+sum[state[i]]\}\) \(sum[i...

题目： poj3045 Cow Acrobats 解析： 贪心题，类似于国王游戏 考虑两个相邻的牛\(i\),\(j\) 设他们上面的牛的重量一共为\(sum\) 把\(i\)放在上面，危险值分别为\(x_1=sum-s_i\),$ x_2=sum+w_i-s_j$ 把\(j\)放在上面，危险值分别为\(x_3=sum-s_j\), \(x_4=sum+w_j-s_i\) 若把j放在上面更优，则有\(max(x_3,x_4)<max(x_1,x_2)\) 有四种情况 \(x_3<x_1\) \(x_3<x_2\) \(x_4<x_1\) \(x_4<x_2\...

题目： #10172. 「一本通 5.4 练习 1」涂抹果酱 解析： 三进制的状压DP 经过简单的打表发现，在\(m=5\)时最多有\(48\)种合法状态 然后就向二进制一样枚举当前状态和上一层的状态进行转移就好了 由于第\(k\)行是给定的，所以转移时要特判一下第\(k\)行，并且注意下一\(k=1\)的情况 设\(f[i][j]\)表示第\(i\)行\(j\)状态时的方案数 \(f[i][j] += f[i - 1][k],k是上一行的状态\) 代码： #include <bits/stdc++.h> #define int long long using names...

国庆不放假，牛客始摸鱼。