题意

给你

n

个数，分成

3

组，输出最大的那一组与最小的那一组的差的最小值。

思路

每个数会加到第一个数或第二个数中或第三个数中，明显考虑动态规划。
$dp_{0,0}$ 的初始值为 $1$ 。
$dp_{j,k}$ 表示第一个数为 $j$ ，第二个数为 $k$ 是否可以。那么 $dp_{j,k}$ 就会由 $dp_{j,k−a_{i}},dp_{j−a_i,k}$ 转移得到。
一个数只能用一次，我们得把可以转移为 $1$ 的 $dp_{j,k}$ 设为一个另外的数，与 $a_i$ 有关的状态转移后，把所有答案为此数的状态再设为 $1$ 。
我们枚举所有的 $dp_{j,k}$ ，和为 $sum$ ，那第三个数自然就是 $sum−j−k$ ，我们记录所有 $dp_{j,k}=1$ 的状态的最小值。

代码

CPP

#include <bits/stdc++.h>
using namespace std;
int T, n, p, a[100], dp[650][650];
int main() {
	cin >> T;
	while(T--) {
		p++;
		cin >> n;
		int sum = 0;
		for(int i = 1; i <= n; i++) {
			cin >> a[i];
			sum += a[i];
		}
		memset(dp, 0, sizeof(dp));
		dp[0][0] = 1;
		for(int i = 1; i <= n; i++) {
			for(int j = sum; j >= a[i]; j--) {
				for(int k = 0; k <= sum; k++) {
					if(dp[j - a[i]][k] == 1) {
						dp[j][k] = 2;
					}
				}
			}
			for(int j = sum; j >= a[i]; j--) {
				for(int k = 0; k <= sum; k++) {
					if(dp[k][j - a[i]] == 1) {
						dp[k][j] = 2;
					}
				}
			}
			for(int j = 0; j <= sum; j++) {
				for(int k = 0; k <= sum; k++) {
					if(dp[j][k] == 2) {
						dp[j][k] = 1;
					}
				}
			}
		}
		int minn = 1e9;
		for(int i = 0; i <= sum; i++) {
			for(int j = 0; j <= sum; j++) {
				if(dp[i][j]) {
					int k = sum - i - j;
					minn = min(minn, abs(max(i, max(j, k)) - min(i, min(j, k))));
				}
			}
		}
		cout<<"Case "<<p<<": "<<minn<<endl;
	}
	return 0;
}

题解：UVA10482 The Candyman Can

文章操作

题意

思路

代码

相关推荐

评论

题解：UVA10482 The Candyman Can