FZYZOJ1001 搭建双塔 【动态规划】

tonyfang posted @ 2015年8月30日 18:22 in FZYZOJ with tags c++ FZYZOJ , 298 阅读

Description

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”。

Input Format

输入第一行为一个数N,表示水晶的数量。第二行为N个数,第i个数表示第i个水晶的高度。

Output Format

输出仅包含一行,如果能搭成一座双塔,则输出双塔的最大高度,否则输出一个字符串“Impossible”。

Sample Input

5
1 3 4 5 2

Sample Output

7

 

【题解】

动态规划,设$f[i,j]$表示,到第$i$个水晶,两个塔高度差$j$,高塔的最高高度。

那么$f[i,j]=f[i-1,j]$(不用这块水晶)

$f[i,j]=max(f[i,j],f[i-1,j-h[i]]+h[i]) (0 \leq j-h[i])$(用这块水晶叠到高塔上)

$f[i,j]=max(f[i,j],f[i-1,j+h[i]]) (j+h[i] \leq total_h)$ (用这块水晶叠到矮塔上,但是矮塔还是矮塔)

$f[i,j]=max(f[i,j],f[i-1,h[i]-j]+j) ( 0 \leq h[i]-j)$ (用这块水晶叠到矮塔上,矮塔变成高塔)

那么就可以写代码啦

 

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int n,h[101],f[101][2010],tt;
int main() {
	int i;memset(f,-1,sizeof(f));
	for(scanf("%d",&n),i=1;i<=n;++i)scanf("%d",&h[i]),tt+=h[i];
	for (f[0][0]=0,i=1;i<=n;++i) {
		for (int j=0;j<=tt;++j) {
			if(f[i-1][j]>=0) f[i][j]=f[i-1][j];
			if(j-h[i]>=0&&f[i-1][j-h[i]]>=0) f[i][j]=max(f[i][j],f[i-1][j-h[i]]+h[i]);
			if(h[i]-j>=0&&f[i-1][h[i]-j]>=0) f[i][j]=max(f[i][j],f[i-1][h[i]-j]+j);
			if(j+h[i]<=tt&&f[i-1][j+h[i]]>=0) f[i][j]=max(f[i][j],f[i-1][j+h[i]]);
		}
	}
	if(f[n][0]>0)printf("%d\n",f[n][0]);else puts("Impossible");
} 

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter