作者提醒：不要复制全文，否则可能产生预期以外的后果。 Difficulty：3.2 / Easy 想了几个非多项式做法，发现状态数都在 2302^{30}230 以上。于是考虑多项式做法。 令 m=Bi3m=\frac{B_i}{3}m=3Bi 。 考虑朴素的背包 DP。定义 dp[i][C1][C2][C3]dp[i][C_1][C_2][C_3]dp[i][C1 ][C2 ][C3 ] 为前 iii 个人，第 jjj 个小组总贡献值为 CjC_jCj 的最少更换次数。 发现这么做是对的。转移只需要看除第一维外任意一维减 BiB_iBi 的情况即可。答案就是 dp[n][m][m][m]dp[n][m][m][m]dp[n][m][m][m]。 但是我们发现这么定义，状态数量是 O(nm3)O(nm^3)O(nm3) 的，总状态数为 100×5003=1.25×1010100\times 500^3=1.25\times 10^{10}100×5003=1.25×1010，不能接受。 但是注意到这里有大量无用的状态，因为对于前 iii 个数，C1+C2+C3=∑j=1iBjC_1+C_2+C_3=\sum_{j=1}^i B_jC1 +C2 +C3 =∑j=1i Bj ，其它的状态一定不合法。 我们考虑只记录 C1,C2C_1,C_2C1 ,C2 ，因为此时 C3C_3C3 的值已经固定。显然这样减少了大量的无用状态。 这样，我们就将复杂度从 O(nm3)O(nm^3)O(nm3) 降到了 O(nm2)O(nm^2)O(nm2)，状态数为 100×5002=2.5×107100\times 500^2=2.5\times 10^7100×5002=2.5×107，可以通过。 进一步地，我们可以滚动数组，使得空间复杂度降至 O(m2)O(m^2)O(m2)，不过前面的已经可以通过，就没必要写了。 时间复杂度：O(nm2)O(nm^2)O(nm2)。