f表示用前i个数中的若干个搭两个高度差为j的塔，矮塔的最大高度

然后动归就可以了

coldwing牛哥,应该是F表示........此时低踏的最大直吧

DP

同Coldwings大牛的方法

只是补充一点：

对状态转移的考虑要全面

偶就因为没考虑全wa了n多次:(

设计函数f(i,j)表示

用前i颗水晶放两个塔，高塔与低塔的差距为j，此时低塔的最低高度

很显然 所求的答案就是f(n,0)

import java.lang.Math.*;
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] height = new int[n + 1];
        int i;
        for (i = 1; i <= n; i++) height[i] = sc.nextInt();
        int ans = maxDoubleTower(height, n);
        if (ans == -1) {
            System.out.println("Impossible"); 
            return;
        }
        System.out.println(ans);
    }
    
    public static int maxDoubleTower(int[] height, int n) {
        int[][] dp = new int[n + 1][2048];
        int[] s = new int[n + 1];
        int i, j;
        for (i = 1; i <= n; i++) {
            s[i] = s[i-1] + height[i];
        }
        
        for (i = 0; i <= n; i++) {
            for (j = 0; j <= 2047; j++) dp[i][j] = -2048;
        }
        dp[0][0] = 0;
        for (i = 1; i <= n; i++) {
            for (j = 0; j <= s[i]; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= height[i]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-height[i]]);
                }
                
                if (j <= height[i]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][height[i]-j] + height[i] - j);
                }
                
                if (j + height[i] <= s[i-1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j + height[i]] + height[i]);
                }
            }
        }
        
        return (dp[n][0] > 0 ? dp[n][0] : -1);
    }
}
/*
s[i] refers to the sum of crystal from 1 to i
dp[i][j] refers to the maximum height of the lower tower when using the first
i pieces of crystal and with a height difference of j
case 1: ignore piece i dp[i][j] = dp[i-1][j]
case 2: put on the higher tower dp[i][j] = dp[i-1][j-height[i]]  condition j >= height[i]
case 3: put on the lower tower without changing the height order
    dp[i][j] = dp[i-1][j+height[i]] + height[i] condition j+height[i] <= s[i]
case 4: put on the lower tower but the lower tower becomes the taller one
    dp[i][j] = dp[i-1][height[i] - j] + height[i] - j condition height[i] >= j
*/

分析后这道题其实很简单
其实我的程序有点**暴力枚举**的思想（受到了机房某大佬启发）
var n,i,j,k,m,v:longint;
a:array[0..10000] of longint;
f:array[0..2000,0..2000] of boolean;
begin
readln(n);
for i:=1 to n do
read(a[i]);
f[0,0]:=true;
for i:=1 to n do
begin
m:=m+a[i];
for j:=m downto 0 do
for k:=m downto 0 do
if f[j,k]=true then
begin
f[j+a[i],k]:=true;
f[j,k+a[i]]:=true;
end;
end;
for i:=m downto 1 do
if f[i,i] then
begin
writeln(i);
halt;
end;
writeln('Impossible');
end.

asdf

#include <iostream>
#include <cstring>
using namespace std;
bool d[2001][2001];//d[i][j]=d[i-h[k]][j]||d[i][j-h[k]]||d[i][j]
long h[201];
int main()
{
long n,i,j,k;
cin>>n;
for (i=1;i<=n;i++) cin>>h[i];
memset(d,false,sizeof(d));
d[0][0]=true;
for (k=1;k<=n;k++)
for (i=2000;i>=0;i--)
for (j=2000;j>=0;j--){
if (i>=h[k]) d[i][j]=d[i][j] || d[i-h[k]][j];
if (j>=h[k]) d[i][j]=d[i][j] || d[i][j-h[k]];
}
for (i=2000;i>=1;i--)
if (d[i][i]) {cout<<i; return 0;}
cout<<"Impossible\n";
return 0;
}

#include <iostream>
#include <cstring>
using namespace std;
bool d[2001][2001];//d[i][j]=d[i-h[k]][j]||d[i][j-h[k]]||d[i][j]
long h[201];
int main()
{
long n,i,j,k;
cin>>n;
for (i=1;i<=n;i++) cin>>h[i];
memset(d,false,sizeof(d));
d[0][0]=true;
for (k=1;k<=n;k++)
for (i=2000;i>=0;i--)
for (j=2000;j>=0;j--){
if (i>=h[k]) d[i][j]=d[i][j] || d[i-h[k]][j];
if (j>=h[k]) d[i][j]=d[i][j] || d[i][j-h[k]];
}
for (i=2000;i>=1;i--)
if (d[i][i]) {cout<<i; return 0;}
cout<<"Impossible\n";
return 0;
}

#include<iostream>
using namespace std;
int dp[2001]={0};//dp[高度差]=高塔高度 
int a[101]={0};//水晶高度
int n=0;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=0;i<=n;i++)
    {
        int dp2[2001]={0};//保存放完水晶后高塔高度 
        for(int j=0;j<=2000;j++) 
        {
            if(dp[j]!=0)//存在这个状态
            {
                if(dp[j+a[i]]<dp[j]+a[i]&&dp2[j+a[i]]<dp[j]+a[i])//把水晶放在高塔上 
                    dp2[j+a[i]]=dp[j]+a[i];
                if(j>=a[i]&&dp[j-a[i]]<dp[j]&&dp2[j-a[i]]<dp[j])//把水晶放在矮塔上 
                    dp2[j-a[i]]=dp[j];
                if(j<a[i]&&dp[a[i]-j]<dp[j]-j+a[i]&&dp2[a[i]-j]<dp[j]-j+a[i])//把水晶放在矮塔上
                    dp2[a[i]-j]=dp[j]-j+a[i];
            }
        }
        if(dp[a[i]]<a[i]&&dp2[a[i]]<a[i])//只放这个水晶 
            dp2[a[i]]=a[i];
        for(int j=0;j<=2000;j++)//反馈新的状态 
            if(dp2[j]!=0)
                dp[j]=dp2[j];
    }
    if(dp[0]==0)
        cout<<"Impossible";
    else
        cout<<dp[0];
    return 0;
}

//很容易的基础题哦

#include <cstdio>
#include <algorithm>
#include <limits>
using namespace std;
int main()
{
    int n,a[101],f[101][2001],h=0;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        h+=a[i];
    }
    for (int i=0;i<=n;i++)
        for (int j=0;j<=h;j++)
            f[i][j]=(numeric_limits<int>::min)();
    f[0][0]=0;
    for (int i=1;i<=n;i++)
        for (int j=h;j>=0;j--)
        {
            f[i][j]=max(f[i][j],f[i-1][j]);
            f[i][j]=max(f[i][j],f[i-1][j+a[i]]+a[i]);
            if (j>=a[i])
                f[i][j]=max(f[i][j],f[i-1][j-a[i]]);
            else
                f[i][j]=max(f[i][j],f[i-1][a[i]-j]+a[i]-j);
        }
    if (f[n][0]<=0)
        printf("%s","Impossible");
    else
        printf("%d\n",f[n][0]);
}

都比了。。第四个点WA了半天后才发现。。dp[n][0]>0?printf("%d\n",dp[n][0]):printf("Impossible\n");写成了dp[n][0]!=-1?printf("%d\n",dp[n][0]):printf("Impossible\n");。。论不能看串题解。。。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

int n;

int dp[200][3000];
int t[3000],ans;

int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&t[i]);
}
if(n<2){
printf("Impossible\n");
return 0;
}
for(int i=0;i<=2000;i++)dp[0][i]=-0x3f3f3f3f;
dp[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=2000;j++){
dp[i][j]=max(dp[i-1][j+t[i]],dp[i-1][j]);
if(j>=t[i])dp[i][j]=max(dp[i][j],dp[i-1][j-t[i]]+t[i]);
else dp[i][j]=max(dp[i][j],dp[i-1][t[i]-j]+j);
}
}
dp[n][0]>0?printf("%d\n",dp[n][0]):printf("Impossible\n");
}

夜黑发题解 By LJH
P1037搭建双塔Accepted
记录信息
评测状态 Accepted
题目 P1037 搭建双塔
递交时间 2016-08-05 23:33:10
代码语言 Pascal
评测机 ShadowShore
消耗时间 45 ms
消耗内存 1708 KiB
评测时间 2016-08-05 23:33:11
评测结果
编译成功

Free Pascal Compiler version 3.0.0 [2015/11/16] for i386
Copyright (c) 1993-2015 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
foo.pas(31,8) Warning: Variable "sum" does not seem to be initialized
Linking foo.exe
45 lines compiled, 0.1 sec, 65472 bytes code, 4100 bytes data
1 warning(s) issued
测试数据 #0: Accepted, time = 0 ms, mem = 1708 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1704 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 1704 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1708 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1708 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1700 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 1704 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 1704 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1704 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 1704 KiB, score = 10
Accepted, time = 45 ms, mem = 1708 KiB, score = 100
代码
{
若设f[i][j]表示第i个物品高度差为j时的max_小的那一组的高度
则状态转移
f[i][j]
不选
one f[i-1][j]
选
two 加在大的上 f[i-1][j-h[i]]
加在小的上
three 小的高度还是小 f[i-1][j+h[i]]+h[i];
four 小的高度大于高的 f[i-1][h[i]-j]+h[i]-j;

f[i][j]=max(f[i-1][j],f[i-1][j-h[i]],f[i-1][j+h[i]]+h[i],f[i-1][h[i]-j]+h[i]-j);

}
uses math;
var
n,i,j,sum:longint;
flag:boolean;
h:array[0..100]of longint;
f:array[0..100,0..2000]of longint;

begin
readln(n);
for i:=0 to n do
for j:=1 to 2000 do f[i][j]:=-maxlongint;
for i:=1 to n do read(h[i]);
for i:=1 to n do
begin
sum:=sum+h[i];
for j:=0 to sum do
begin
f[i][j]:=max(f[i-1][j],f[i-1][j+h[i]]+h[i]);
flag:=false;
if j-h[i]>=0 then flag:=true;
if flag then f[i][j]:=max(f[i][j],f[i-1][j-h[i]]);
flag:=false;
if h[i]-j>=0 then flag:=true;
if flag then f[i][j]:=max(f[i][j],f[i-1][h[i]-j]+h[i]-j);
end;
end;
if f[n][0]<>0 then writeln(f[n][0]) else
writeln('Impossible');
end.

终于知道为什么是 sum downto 0 do 而不是 0 to sum do 了

、、、

#include<cstdio>
int f0[2001],f1[2001],p=1,q=0,n,h;
int main()
{
scanf("%d",&n);
for(int i=1;i<=2000;++i)
f0[i]=f1[i]=-2147483647;
while(n--)
{
scanf("%d",&h);
for(int i=h;i<=2000;++i)
f1[i]=std::max(f1[i],f0[i-h]);
for(int i=0,j=2000-h;i<=j;++i)
f1[i]=std::max(f1[i],f0[i+h]+h);
for(int i=0;i<h;++i)
f1[i]=std::max(f1[i],f0[h-i]+h-i);
for(int i=0;i<=2000;++i)
f0[i]=f1[i];
}
if(f0[0])
printf("%d\n",f0[0]);
else
puts("Impossible");
return 0;
}

program vijos1037;
var
f:array[0..100,0..2000] of longint;
ans,n,m,i,j,k,hh:longint;
h:array[0..100] of longint;
procedure init;
begin
readln(n);
for i:=1 to n do
begin
read(h[i]);
hh:=h[i]+hh;
end;
end;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
procedure work;
begin
for i:=0 to n do
for j:=0 to hh do
f[i,j]:=-maxlongint;
f[0,0]:=0;
for i:=1 to n do
for j:=hh downto 0 do
begin
if j>h[i] then
f[i,j]:=max(f[i-1,j],max(f[i-1,j-h[i]]+h[i],f[i-1,j+h[i]]));
if j<=h[i] then
f[i,j]:=max(f[i-1,j],max(f[i-1,h[i]-j]+j,f[i-1,h[i]+j]));
end;
ans:=f[n,0];
if f[n,0]<=0 then writeln('Impossible') else write(ans);
end;
begin
init;
work;
end.

数据弱了......
4
5 1 2 1
输出3
结果AC了......

动规思路：1.f[i][j]表示前i块水晶，高度差为j时，较矮的塔的高度，sum[i]表示前缀和
2.对于第i块水晶有四种操作：加在高塔上；加在低塔上，但仍为低塔；加在低塔上，成为高塔；
不放这块水晶。
3.f[i][j]从f[i-1][h]推来，就要从以上四种情况中确定h
4.把f[i][j]初始化为负数，因为要保证f[i-1][h]这种情况是存在的，sum[ ]也是为了保证情况存在。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
int N;
int a[300],sum[300];
int f[300][2500];
int main(){
memset(f,-0x7f,sizeof(f));
cin>>N;
for(int i=1;i<=N;i++){
cin>>a[i];
}
sort(a+1,a+N+1);
for(int i=1;i<=N;i++) sum[i]=sum[i-1]+a[i];
f[1][0]=0;f[1][a[1]]=0;
for(int i=2;i<=N;i++){
for(int j=0;j<=sum[i];j++){

int h1=j-a[i];
if(h1>=0&&h1<=sum[i-1])
f[i][j]=max(f[i][j],f[i-1][h1]);

int h2=j+a[i];
if(h2<=sum[i-1])
f[i][j]=max(f[i][j],f[i-1][h2]+a[i]);

int h3=a[i]-j;
if(h3>=0&&h3<=sum[i-1])
f[i][j]=max(f[i][j],f[i-1][h3]+h3);

int h4=j;
if(h4<=sum[i-1])
f[i][j]=max(f[i][j],f[i-1][j]);
}
}
if(f[N][0]<=0){
cout<<"Impossible";
return 0;
}
cout<<f[N][0];
return 0;
}

数据太弱了...
WA掉第一个点的童鞋试试 5 1 2 1 这个数据..