描述

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

输入格式

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

输出格式

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

题解

应该说是很简单的dp,但是我没有独立完成……说明我果然是巨菜啊……

状态表示是我没见过的-_-。。。看了下别人的状态表示,然后就很容易地写出了方程。

dp(i,j)表示用前i块水晶堆2个塔,两塔间高度差为j时,较低塔的最大高度。

\begin{equation*} 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)\} \end{equation*}

注意处理边界……我还因为边界问题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;
}