题解：UVA10482 The Candyman Can

问题

$T$ 组数据，每组数据给你 $n$ 个数，把这 $n$ 个数分成三个部分，问总和最大与最小的差值最小是多少。

思路

考虑到 $n \le 32$，直接暴力枚举。

优化：枚举两个部分，第三个部分可以通过总和与前两个部分相减求出。

设 $f_{i, j}$ 为第一个部分总和为 $i$，第二个部分总和为 $j$ 的第三个部分是否可行。

那么开始暴力枚举，如果 $f_{i, j}$ 可以，那么第三部分加上这个数也可以。

代码

#include <bits/stdc++.h>
using namespace std;
int T, n, ans, sum, a[35];
bool f[105][105];
int main()
{
    cin >> T;
    for (_ = 1; _ <= T; _++) // 使用 while(T--) _++; 也可以
    {
        ans = INT_MAX, sum = 0;
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            sum += a[i];
        }
        memset(f, 0, sizeof(f));
        f[0][0] = 1;
        for (int i = 1; i <= n; i++)
        {
            for (int j = sum; j >= 0; j--)
            {
                for (int k = sum; k >= 0; k--)
                {
                    if (f[j][k]) // 如果可以
                    {
                        f[j + a[i]][k] = true; // 那么加上这个数也可以
                        f[j][k + a[i]] = true; // 反存
                    }
                }
            }
        }
        for (int i = 0; i <= sum; i++)
        {
            for (int j = 0; j <= sum; j++)
            {
                if (f[i][j]) // 可行
                {
                    int x = min(min(i, j), sum - i - j); // 总和最小的分组
                    int y = max(max(i, j), sum - i - j); // 总和最大的分组
                    ans = min(ans, y - x);               // 记录差值最小的答案
                }
            }
        }
        printf("Case %d: %d\n", _, ans); // 使用 cout << "Case " << _ << ": " << ans << endl; 也可以
    }
    return 0;
}