Vijos P1153 - 猫狗大战
传送门
题意
把给定的数分成两部分，最多只能相差1个，使得他们的差最小。
思路
记得在UVa上有一题，分成两部分使得差最小，那直接对sum的一半进行背包即可，这题算是那题的升级版吧。
用$dp[i][j][k]$表示前i个选j个能否到达k，数据太大，滚一下。
代码
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
const int MAXN = 200 + 10;
const int INF = 0x3f3f3f3f;
int w[MAXN];
bool dp[MAXN][MAXN * 40 + 10];
int main()
{
//freopen("input.txt", "r", stdin);
int n, i, j, sum = 0;
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
scanf("%d", &w[i]);
sum += w[i];
}
dp[0][0] = 1;
for (i = 1; i <= n; i++)
for (j = n; j >= 1; j--)
for (int k = sum; k >= w[i]; k--)
dp[j][k] |= dp[j - 1][k - w[i]];
int t = sum >> 1;
n >>= 1;
for (i = t; i >= 0; i--)
if (dp[n][i])
{
printf("%d %d\n", i, sum - i);
return 0;
}
return 0;
}