Vijos P1037 - 搭建双塔
传送门
思路
参考了别人的题解。
用$dp[i][j]$, i和j表示两座塔的高度，值为1或者0。
枚举所有两座塔的高度，最后取最大的dp[i][i]即可。
代码
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
const int MAXN = 2000 + 10;
const int INF = 0x3f3f3f3f;
int dp[MAXN][MAXN];
int main()
{
//freopen("input.txt", "r", stdin);
int n, i, j, cur = 0, a;
scanf("%d", &n);
dp[0][0] = 1;
for (i = 0; i < n; i++)
{
scanf("%d", &a);
for (j = cur; j >= 0; j--)
for (int k = cur; k >= 0; k--)
{
dp[j + a][k] |= dp[j][k];
dp[j][k + a] |= dp[j][k];
}
cur += a;
}
for (i = cur; i >= 1; i--)
if (dp[i][i])
{
printf("%d\n", i);
return 0;
}
printf("Impossible\n");
return 0;
}