搭建双塔
【描述 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
【题解 Solution】
应该说是很简单的dp，但是我没有独立完成……说明我果然是巨菜啊……
状态表示是我没见过的-_-。。。看了下别人的状态表示，然后就很容易地写出了方程。
dp(i,j)表示用前i块水晶堆2个塔，两塔间高度差为j时，较低塔的最大高度。
dp(i,j)=max{ dp(i-1,j+h[i]),dp(i-1,j-h[i])+h[i],dp(i-1,h[i]-j)+j,dp(i-1,j) }
注意处理边界……我还因为边界问题WA了一次，sigh……
源码：
#include <fstream>
#include <iostream>
#include <climits>
#include <cassert>
using namespace std;
int N,H[101],dp[101][2001];
bool flag[101][2001];
int memo(int i,int j){
if(j<0) return INT_MIN;
if(i==0&&j==0) return 0;
if(i==0) return INT_MIN;
assert(i<=N&&j<=2000);
if(flag[i][j]) return dp[i][j];
int ans=INT_MIN;
if(ans<memo(i-1,j)) ans=memo(i-1,j);//do not put
if(ans<memo(i-1,j+H[i])) ans=memo(i-1,j+H[i]);//put on the higher
if(ans<memo(i-1,j-H[i])+H[i]) ans=memo(i-1,j-H[i])+H[i];//put on the lower
if(ans<memo(i-1,H[i]-j)+j) ans=memo(i-1,H[i]-j)+j;//put on the lower,and it becomes the higher
flag[i][j]=true;
return dp[i][j]=ans;
}
int main(){
//The Amulet
unsigned rp=unsigned(-1);
//ifstream cin("input.txt");
cin >> N;
for(int i=1;i<=N;i++) cin >> H[i];
int ans = memo(N,0);
if(ans<=0) cout << "Impossible" << endl;
else cout << ans << endl;
return 0;
}
可能你对下面的文章也感兴趣：
最近评论