问题描述
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]=max{f[i-1,j],
f[i-1,j+v[i]],
f[i-1,j-v[i]]+v[i],(j-v[i]>=0)
f[i-1,abs(j-v[i])]-abs(j-v[i])+v[i],(j-v[i]<0)}
答案就是f[n,0]
如果f[n,0]=0就impossible
【代码】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | #include <stdio.h> #define max(a,b) (a>b ? a:b) int main() { int n, m = 0, i, j; int h[101]; int dp[101][2001] = {0}; scanf("%d",&n); for(i = 1; i <= n; i++) { scanf("%d", &h[i]); m += h[i]; } for (i = 1; i <= n; i++) for (j = 0; j <= m; j++) { dp[i][j] = dp[i-1][j]; if(j == h[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - h[i]] + h[i]); if(j < h[i] && dp[i - 1][h[i] - j] -h[i] + j >= 0) dp[i][j] = max(dp[i][j], dp[i - 1][h[i] - j] + j); if(j > h[i] && dp[i - 1][j - h[i]] + h[i] - j >= 0) dp[i][j] = max(dp[i][j], dp[i - 1][j - h[i]] + h[i]); if(j + h[i] <= m) dp[i][j] = max(dp[i][j], dp[i - 1][j + h[i]]); } if(dp[n][0]) printf("%d", dp[n][0]); else printf("Impossible"); return 0; } |