首页 > 代码库 > Laoj P1299 搭建双塔

Laoj P1299 搭建双塔

2024-11-19 12:49:40   206人阅读

 

试题描述
　　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”。
输入示例
5
1 3 4 5 2
输出示例
7
试题来源
某校NOIP模拟题
vijos1037

 

【分析】

dp[i][j]=true表示第一座塔可以达到高度i，第二座塔可以达到高度j。

如果dp[i][j]=true，那么dp[i+a[t]][j]和dp[i][j+a[t]]也为true（每块水晶只能用在一座塔上）。

最后从高到低枚举即可。

 

【代码】

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int n, a[105], dp[2020][2020], sum;
 5 bool flag;
 6 
 7 void init() {
 8     cin >> n;
 9     for (int i=1;i<=n;++i) {
10         cin >> a[i];
11         sum+=a[i];
12     }
13 }
14 
15 void sovle() {
16     sum/=2;
17     sum++;
18     dp[0][0]=true;
19     for (int i=1;i<=n;++i)
20         for (int j=sum;j>=0;--j)
21             for (int k=sum;k>=0;--k)
22                 if (dp[j][k])
23                     dp[j+a[i]][k]=dp[j][k+a[i]]=true;
24     for (int i=sum;i>0;--i) {
25         if (dp[i][i]) {
26             flag=true;
27             cout << i << endl;
28             break;
29         }
30     }
31     if (!flag)
32         cout << "Impossible" << endl;
33 }
34 
35 int main() {
36     init();
37     sovle();
38 }

 

Laoj P1299 搭建双塔


联系
我们