E

题目大意：

\(n\)个人，每个人初始在第\(a_i\)组，有一个力量值\(b_i\)。需要调整某些人到其他组去，使得每个组的力量值相等。若能，求出最少调整的人数。若不能，输出\(-1\)。\(n\leq 100,1\leq b_i,\sum b_i \leq 1500,a_i\in\{1,2,3\}\)。

分析：

暴力dfs显然不行，还要求最少调整的人数，只能是dp了呀！至于dp的状态，题目里面就只有\(a_i\)和\(b_i\)，显然就用\(b_i\)来设状态。设\(dp[i][x][y]\)表示考虑到第\(i\)个人，前\(i-1\)个人的第一组的力量值之和为\(x\)，第二组的力量值之和为\(y\)。此处特别注意：\(i\)这一维是有必要的，不可以省略！因为转移过程为：前\(i-1\)个的和分别是\(x\)和\(y\)，然后考虑当前的\(i\)放在那一组后进行转移。如果没有\(i\)这一维，意味着无法体现一个一个考虑的过程了，即自己可以贡献自己，这是不行的！用滚动数组优化，复杂度\(O(n(\sum b_i) ^ 2)\)。

代码：

#include <bits/stdc++.h>

using namespace std;

int n, s[4], a[105], b[105], dp[2][1505][1505];

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++ ) scanf("%d%d", &a[i], &b[i]), s[a[i]] += b[i], s[0] += b[i];
	if (s[0] % 3) {puts("-1"); return 0;}
	memset(dp, 0x3f, sizeof(dp)); dp[0][s[1]][s[2]] = dp[1][s[1]][s[2]] = 0;
	for (int k = 1; k <= n; k ++ )
	{
		int o = (k & 1);
		for (int i = 0; i <= 1500; i ++ )
		{
			for (int j = 0; j <= 1500; j ++ )
			{
				dp[o][i][j] = min(dp[o][i][j], dp[o ^ 1][i][j]);
				if (a[k] == 1)
				{
					if (i >= b[k] && j + b[k] <= 1500) dp[o][i - b[k]][j + b[k]] = min(dp[o][i - b[k]][j + b[k]], dp[o ^ 1][i][j] + 1);
					if (i >= b[k]) dp[o][i - b[k]][j] = min(dp[o][i - b[k]][j], dp[o ^ 1][i][j] + 1);
				}
				if (a[k] == 2)
				{
					if (i + b[k] <= 1500 && j >= b[k]) dp[o][i + b[k]][j - b[k]] = min(dp[o][i + b[k]][j - b[k]], dp[o ^ 1][i][j] + 1);
					if (j >= b[k]) dp[o][i][j - b[k]] = min(dp[o][i][j - b[k]], dp[o ^ 1][i][j] + 1);
				}
				if (a[k] == 3)
				{
					if (i + b[k] <= 1500) dp[o][i + b[k]][j] = min(dp[o][i + b[k]][j], dp[o ^ 1][i][j] + 1);
					if (j + b[k] <= 1500) dp[o][i][j + b[k]] = min(dp[o][i][j + b[k]], dp[o ^ 1][i][j] + 1);
				}
			}
		}
	}
	printf("%d\n", dp[n & 1][s[0] / 3][s[0] / 3] > n ? -1 : dp[n & 1][s[0] / 3][s[0] / 3]);
	return 0;
}