vijos 1037 搭建双塔简单DP

2001年9月11日，一场突发的灾难将纽约世界贸易中心大厦夷为平地，Mr. F曾亲眼目睹了这次灾难。为了纪念“9 11”事件，Mr. F决定自己用水晶来搭建一座双塔。
　　Mr. F有N块水晶，每块水晶有一个高度，他想用这N块水晶搭建两座有同样高度的塔，使他们成为一座双塔，Mr. F可以从这N块水晶中任取M（1≤M≤N）块来搭建。但是他不知道能否使两座塔有同样的高度，也不知道如果能搭建成一座双塔，这座双塔的最大高度是多少。所以他来请你帮忙。

　　给定水晶的数量N（1≤N≤100）和每块水晶的高度Hi（N块水晶高度的总和不超过2000），你的任务是判断Mr. F能否用这些水晶搭建成一座双塔（两座塔有同样的高度），如果能，则输出所能搭建的双塔的最大高度，否则输出“Impossible”。

一看就跟背包有些类似，实际上确实是个很简单的DP

用dp[i][j] 表示的是前i个水晶，凑成的两塔高度差为j的较低塔的最大高度。

那么它的状态可能由四种情况转化而来

1.该物品没用上

2.低塔加上了该物品还是低塔

3.高塔加上了该物品边的更高了

4.低塔加上了该物品变成了高塔

这里我们可以画几个图，就清晰许多了

转移方程请看代码

[cpp] view plaincopyprint #include
#include
#include
#include
#include
#include
#include
#include
#include
#define MAXN 777
#define MAXM 400005
#define INF 1000000007
using namespace std;
int n;
int f[111][2222], c[111];
int main()
{
scanf("%d", &n);
int sum = 0;
for(int i = 1; i <= n; i++)
{
scanf("%d", &c[i]);
sum += c[i];
}
memset(f, -1, sizeof(f));
f[0][0] = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 0; j <= sum; j++)
{
if(f[i - 1][j] != -1) f[i][j] = f[i - 1][j];
if(j + c[i] <= sum && f[i - 1][j + c[i]] != -1)
f[i][j] = max(f[i][j], f[i - 1][j + c[i]] + c[i]);
if(j >= c[i] && f[i - 1][j - c[i]] != -1)
f[i][j] = max(f[i][j], f[i - 1][j - c[i]]);
if(c[i] > j && f[i - 1][c[i] - j] != -1)
f[i][j] = max(f[i][j], f[i - 1][c[i] - j] + c[i] - j);
}
}
if(f[n][0] > 0) printf("%d\n", f[n][0]);
else printf("Impossible\n");
return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MAXN 777
#define MAXM 400005
#define INF 1000000007
using namespace std;
int n;
int f[111][2222], c[111];
int main()
{
scanf("%d", &n);
int sum = 0;
for(int i = 1; i <= n; i++)
{
scanf("%d", &c[i]);
sum += c[i];
}
memset(f, -1, sizeof(f));
f[0][0] = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 0; j <= sum; j++)
{
if(f[i - 1][j] != -1) f[i][j] = f[i - 1][j];
if(j + c[i] <= sum && f[i - 1][j + c[i]] != -1)
f[i][j] = max(f[i][j], f[i - 1][j + c[i]] + c[i]);
if(j >= c[i] && f[i - 1][j - c[i]] != -1)
f[i][j] = max(f[i][j], f[i - 1][j - c[i]]);
if(c[i] > j && f[i - 1][c[i] - j] != -1)
f[i][j] = max(f[i][j], f[i - 1][c[i] - j] + c[i] - j);
}
}
if(f[n][0] > 0) printf("%d\n", f[n][0]);
else printf("Impossible\n");
return 0;
}

vijos 1037 搭建双塔 简单DP