var
a:array[0..100] of longint;
f:array[0..2000,0..2000] of boolean;
i,j,k,sum,n:longint;
begin
readln(n);
for i:=1 to n do
read(a[i]);
f[0,0]:=true;
for i:=1 to n do
begin
for j:=sum downto 0 do
for k:=sum downto 0 do
if f[j,k] then
begin
f[j,k+a[i]]:=true;
f[j+a[i],k]:=true;
end;
sum:=sum+a[i];
end;
for i:=sum downto 1 do
if f[i,i] then
begin
writeln(i);
halt;
end;
writeln('Impossible');
end.

点击查看程序源码+详细题解

Var

sum,i,j,k,m,n,l,p,x,y:Longint;

f:Array[0..100,0..200]Of Longint;

a:Array[0..100]Of Longint;

Function max(a,b,c:Longint):Longint;

Begin

If (a>b)And(a>c) Then max:=a Else If b>c Then max:=b Else max:=c;

End;

Begin

Read(n);

For i:=1 To n Do

Begin

Read(a[i]);

sum:=sum+a[i];

End;

//f[1,a[1]]:=0;

For i:=1 To n Do For j:=1 To sum Do f:=-maxlongint Div 10;

f[0,0]:=0;

For i:=2 To n Do

Begin

For j:=sum DownTo 0 Do

Begin

If j>=a[i] Then

f:=max(f,f+a[i],f)

Else

f:=max(f,f+a[i]-j,f+a[i]);

End

End;

Writeln(f[n,0]);

End.

好吧。广搜过了。4000000个状态量。X[],Y[]分别记录第一个塔的高度。第2个塔的高度。用矩阵存1/0表示能否。。最后找到最大的MAP[J][J]就可以了。

#include

using namespace std;

int map[2010][2005],top,xx,yy,x[4001000],y[4001000],a[200];

int cl;

int pd,ans,j,n,i;

int main()

{

    freopen("p1037.in","r",stdin);

    freopen("p1037.out","w",stdout);

    

    scanf("%d",&n);

    

    for(j=1;j

sdf

前面的人都脑残么，那个f明明是较矮塔的最大高度，误导了我好长时间！！！！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

详细过程请点击这里

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 56ms

├ 测试数据 04：答案正确... 88ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 244ms

├ 测试数据 07：答案正确... 244ms

├ 测试数据 08：答案正确... 431ms

├ 测试数据 09：答案正确... 619ms

├ 测试数据 10：答案正确... 650ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2332ms

#include

#include

using namespace std;

bool ma[1001][1001];

int main()

{

int h[101],i,j,n,k;

scanf("%d",&n);

for(i=0;i=0;j--)

{

if(i>=h[k] && ma[i-h[k]][j]) ma[i][j]=true;

if(j>=h[k] && ma[i][j-h[k]]) ma[i][j]=true;

}

for(j=0,k,i=1;i

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|--

Accepted 有效得分：100 有效耗时：0ms

---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|--

program ex;

var n,i,j,ans,z:longint;

a:array[0..100] of longint;

f:array[0..100,-2000..2000] of longint;

function max(x,y:longint):longint;

begin

if x>y then exit(x) else exit(y);

end;

begin

readln(n);

for i:=1 to n do begin read(a[i]);z:=z+a[i];end;readln;

fillchar(f,sizeof(f),128);

f[0,0]:=0;

for i:=1 to n do

for j:=0 to z do

f:=max(max(max(f,f+a[i]),f+j),f);

ans:=-maxlongint;

for i:=1 to n do

ans:=max(ans,f);

if ans

AC10题纪念

交了四次郁闷

不明白为什么快排就AC了啊

此题甚好！

虽然这题是两个塔在比大小。。但实际上我们没有必要记录具体的高度。。只需要记录**高度差**。。因为塔的相对高矮很可能在加入新的h[i]后改变。。

对于每一个h[i]。。很显然只有3种情况：加入第一座塔。。加入第二座塔或者直接pass。。如上文所说。。由于我们只记录高度差。。故而我们需要分析一个新的h[i]对高度差带来的影响。。

经过分析。。新的h[i]只可能对高度差产生3种影响：高度差增加h[i]。。高度差减少h[i]但高度差

不难的背包

var

f:array[0..20000]of longint;

n,i,j,x:longint;

begin

readln(n);

fillchar(f,sizeof(f),0); f[0]:=1;

for i:=1 to n do

begin

read(x);

for j:=200*n downto x do

if f[j-x]>0 then inc(f[j]);

end;

for i:=100*n downto 1 do

if(f[i]>1)and(f>0)then

begin

writeln(i); exit;

end;

writeln('Impossible');

end.

数据太弱，8 3 3 22 就过不了，但也过了~~~~~~~~~

Flag 　　Accepted

题号 　　P1037

类型(?) 　　动态规划

通过 　　3001人

提交 　　11836次

通过率 　　25%

难度 　　2

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 25ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 25ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：75ms

我很弱，祝福我的第一次NOIP

本来是想错了的。。。改的时候突然发现

a[2*i]>0 and a[i]>1 这东西 于是错的变对的了

procedure check;

var i,j,tmp,tmp1:integer;

begin

tmp:=0;tmp1:=0; a[0]:=1;

for i:= 1to n do

begin

tmp:=tmp1;

for j:= tmp downto 0 do

if a[j]>0

then begin

inc(a[j+h[i]]) ;

if j+h[i]>tmp1 then tmp1:=h[i]+j;

end;

end;

top:=tmp1;

end;

begin

fillchar(a,sizeof(a),0);

int;

check;

max:=0;

for i:= top downto 1 do

if (a[i]>1)and(a[2*i]>0) then begin max:=i;break;end;

if max0 then

write(output,max)

else

write(output,'Impossible');

end.

写了个很丑的背包....

不过秒掉了！

---|---|---|---|---|---|---|---|---|---|---|---|-

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

http://www.cnblogs.com/waterfalleagle/archive/2009/11/11/1601206.html

有没有大牛可以秒杀？

请SHOW出来

以f[i, j]表示前i块水晶堆到高度差为j时较高塔的高度，有四种决策：

第i块要堆的时候，

1.不放第i块水晶；

2.放进去后，高塔变矮塔（第i块放在矮塔上了）；

3.放进去后，高塔仍高（第i块放在矮塔上）；

4.放进去后，高塔更高（第i块放在高塔上）。

自己画画图，就出来了

#include

using namespace std;

int f[2][2001];

int c[101];

int n;

int

max( int i1, int i2 )

{

return i1 > i2 ? i1 : i2;

}

int

main()

{

int cur = 0, pre = 0;

int sum = 0;

cin >> n;

for( int i = 1; i > c[i];

sum += c[i];

}

memset( f, -1, sizeof f );

f[0][0] = 0;

for( int i = 1; i = c[i] )

if( f[pre][j - c[i]] > -1 )

f[cur][j] = max( f[pre][j - c[i]] + c[i], f[cur][j] );

if( j + c[i] -1 )

f[cur][j] = max( f[pre][j + c[i]], f[cur][j] );

if( c[i] > j )

if( f[pre][c[i] - j] > -1 )

f[cur][j] = max( f[pre][c[i] - j] + j, f[cur][j] );

}

}

if( f[cur][0] > 0 )

cout

不用dp

O（N）统计

hahahaha

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

C++代码+题解
http://www.cnblogs.com/937337156Zhang/p/6044273.html