LightOJ1126 Building Twin Towers(DP)
题目
Source
http://www.lightoj.com/volume_showproblem.php?problem=1126
Description
Professor Sofdor Ali is fascinated about twin towers. So, in this problem you are working as his assistant, and you have to help him making a large twin towers.
For this reason he gave you some rectangular bricks. You can pick some of the bricks and can put bricks on top of each other to build a tower. As the name says, you want to make two towers that have equal heights. And of course the height of the towers should be positive.
For example, suppose there are three bricks of heights 3, 4 and 7. So you can build two towers of height 7. One contains a single brick of height 7, and the other contains a brick of height 3 and a brick of height 4. If you are given bricks of heights 2, 2, 3 and 4 then you can make two towers with height 4 (just don't use brick with height 3).
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with an integer n (1 ≤ n ≤ 50), denoting the number of bricks. The next line contains n space separated integers, each containing the height of the brick hi (1 ≤ hi ≤ 500000). You can safely assume that the sum of heights of all bricks will not be greater than 500000.
Output
For each case, print the case number and the height of the tallest twin towers that can be built. If it's impossible to build the twin towers as stated, print "impossible".
Sample Input
4
3
3 4 7
3
10 9 2
2
21 21
9
15 15 14 24 14 3 20 23 15
Sample Output
Case 1: 7
Case 2: impossible
Case 3: 21
Case 4: 64
分析
题目大概说有n个各有高度的砖头,要用它们叠出两个高度一样的塔,问高度最多为多少。
- dp[i][j]表示前i个砖头中两塔高度差为j能叠出的最高的那座塔的高度
- dp[n][0]即为所求
- 对于第i个砖头不取、取且叠在低塔上、取且叠在高塔上,从i-1的状态转移
- 另外,空间比较大可以用滚动数组
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int d[2][500100];
int main(){
int t,n,a;
scanf("%d",&t);
for(int cse=1; cse<=t; ++cse){
scanf("%d",&n);
memset(d,-1,sizeof(d));
d[0][0]=0;
int k=0;
for(int i=0; i<n; ++i){
scanf("%d",&a);
memcpy(d[!k],d[k],sizeof(d[k]));
for(int j=0; j<=500000; ++j){
if(d[k][j]==-1) continue;
if(j+a<=500000) d[!k][j+a]=max(d[!k][j+a],d[k][j]+a);
if(a>j){
d[!k][a-j]=max(d[!k][a-j],d[k][j]+a-j);
}else{
d[!k][j-a]=max(d[!k][j-a],d[k][j]);
}
}
k^=1;
}
if(d[k][0]==0) printf("Case %d: impossible\n",cse);
else printf("Case %d: %d\n",cse,d[k][0]);
}
return 0;
}
最新文章
- 初学JAVA的 感想 尹鑫磊
- Sublime无法使用package control安装插件
- 转发!HTML 复选框 checkbox 的 JavaScript 的全选和全反选
- java基础-基本数据类型
- iOS 最全面试题
- [转]Linux进程间通信——使用信号
- Javascript中日期函数的相关操作
- PHP-PCRE正则表达式函数
- asp.net 分析器错误消息: 文件.aspx.cs”不存在错误
- NWERC 2012 Problem E Edge Case
- 采用CXF+spring+restful创建一个web接口项目
- git使用3
- 我的Windows日常——Excel 打开.xls .xlsx 文件格式或文件扩展名无效
- shell实战之Linux主机系统监控
- Java:ConcurrentLinkedQueue的实现原理分析
- linux下反弹shell
- umount /mnt/cdrom
- KMP 初级板子 待更新
- ffmpeg 编码(视屏)
- “Hello World!”团队第五周第五次会议