题解：UVA10482 The Candyman Can

zhangmuning1016 · 2025-01-05 09:39:38 · 题解

题意

给你 n 个数，分成 3 组，输出最大的那一组与最小的那一组的差的最小值。

思路

• 每个数会加到第一个数或第二个数中或第三个数中，明显考虑 动态规划。

• 一个数只能用一次，我们得把可以转移为 1 的 dp_{j,k} 设为一个另外的数，与 a_i 有关的状态转移后，把所有答案为此数的状态再设为 1。

• 我们枚举所有的 dp_{j,k}，和为 sum，那第三个数自然就是 sum−j−k，我们记录所有 dp_{j,k}=1 的状态的最小值。

代码

#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;
}