搭建雙塔，貌似是非常有名的一道題，OI的 dp[i][j]表示使用前i個水晶塊的時候，兩座塔的誤差為j時兩座塔共有的最高高度，對于第i個木塊，有三種情況，第一種不放，第二種放在其中挨塔上，此時更新誤差值以及共有的最高高度值，第三種情況放在高塔上，此時僅僅更新誤差值。   view code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
#define MAX 2500
int n, a[150], sum[150], dp[150][2010], i, j, k;
int max(int c, int a, int b)
{
int x;
if (a > b) x = a;
else x = b;
if (x > c) return x;
else return c;
}
int main()
{
scanf("%d", &n);;
for (i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
sum[i] = sum[i - 1] + a[i];
}
for (i = 0; i < 150; i++)
for (j = 0; j < 2010; j++)
dp[i][j] = -10000;
dp[0][0] = 0;
for (i = 1; i <= n; i++)
for (j = sum[i]; j >= 0; j--)
{
if (a[i] >= j)
dp[i][j] = max(dp[i - 1][j], dp[i - 1][a[i] - j] + j, dp[i - 1][j + a[i]]);
else
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i]] + a[i], dp[i - 1][j + a[i]]);
}
k = -1;
for (i = 1; i <= n; i++)
if (k < dp[i][0]) k = dp[i][0];
if (k > 0) printf("%d\n", k);
else printf("Impossible\n");
return 0;
}
|