244 条题解
-
0
绿色的云 LV 10 @ 2013-05-26 20:03:05
终于秒了 没看到Impossible一直输出0 卡了好久55
VijosEx via JudgeDaemon2/13.5.1.0 via libjudge
编译成功测试数据 #0: Accepted, time = 0 ms, mem = 476 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 476 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 476 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 472 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 476 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 476 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 476 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 472 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 476 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 472 KiB, score = 10
Accepted, time = 0 ms, mem = 476 KiB, score = 100#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;
#define MAXN 100
#define MAXS 1001int k=0;
int f[MAXS][2];
int n;
int a[MAXN];
int sum=0;int main(){
memset(f,0,sizeof(f));
cin>>n;
for (int i=0;i<n;i++){
cin>>a[i];
sum+=a[i];
}
f[0][0]=1;
sum/=2;
for (int i=0;i<n;i++){
for (int j=0;j<=sum;j++){
if (f[j][k]){
f[j][k^1]=max(f[j][k^1],f[j][k]);
if (j>=a[i]) f[j-a[i]][k^1]=max(f[j-a[i]][k^1],f[j][k]+a[i]);
else f[a[i]-j][k^1]=max(f[a[i]-j][k^1],f[j][k]+j);
if (j+a[i]<=sum) f[j+a[i]][k^1]=max(f[j+a[i]][k^1],f[j][k]);
}
}
k^=1;
}
if (f[0][k]-1) cout<<f[0][k]-1<<endl; else cout<<"Impossible"<<endl;
return 0;
} -
0
AC10纪念，刚刚从tyvj的崩溃阴影中走出来…………
测试数据 #0: Accepted, time = 0 ms, mem = 1572 KiB, score = 10测试数据 #1: Accepted, time = 15 ms, mem = 1568 KiB, score = 10
测试数据 #2: Accepted, time = 7 ms, mem = 1568 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 1576 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 1568 KiB, score = 10
测试数据 #5: Accepted, time = 7 ms, mem = 1568 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 1576 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 1572 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 1576 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 1576 KiB, score = 10
Summary: Accepted, time = 120 ms, mem = 1576 KiB, score = 100
代码
program P1037;
var
i,j,sum,n:longint;
dp:array[0..100,0..2000]of longint;
h:array[1..100]of longint;
function max(a,b:longint):longint;
begin
if a>b then
max:=a
else max:=b;
end;
procedure print;
begin
if dp[n,0]>0 then
writeln(dp[n,0])
else writeln('Impossible');
end;
begin
readln(n);
for i:=1 to n do
begin
read(h[i]);
inc(sum,h[i]);
end;
for i:=0 to n do
for j:=0 to sum do
dp[i,j]:=-maxint;
dp[0,0]:=0;
for i:=1 to n do
for j:=sum downto 0 do
begin
if j>h[i] then
dp[i,j]:=max(max(dp[i-1,j],dp[i-1,j-h[i]]+h[i]),dp[i-1,j+h[i]]);
if h[i]>=j then
dp[i,j]:=max(max(dp[i-1,j],dp[i-1,h[i]-j]+j),dp[i-1,j+h[i]]);
end;
print;
end. -
0
var
f:array[-2000..2000,-2000..2000]of boolean;
a:array[1..2000]of longint;
n,m,i,j,k,l,sum,ans:longint;
begin
readln(n);
f[0,0]:=true;
for i:=1 to n do
begin
read(a[i]);
inc(ans,a[i]);
end;
for l:=1 to n do
begin
inc(sum,a[l]);
if sum>ans div 2 then sum:=ans div 2;//小优化for i:=sum downto 0 do
for j:=sum downto 0 dof:=for f[i,j-a[l]]or f[i-a[l],j];
end;
for i:=sum downto 1 do
if f
then begin
write(i);
halt;
end;
write('Impossible');
end. -
0
wangshichuan LV 8 @ 2009-11-06 10:12:03
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 446ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 430ms
├ 测试数据 07：答案正确... 805ms
├ 测试数据 08：运行超时...
├ 测试数据 09：运行超时...
├ 测试数据 10：运行超时... -
0
var
f:array[0..2000,0..2000] of boolean;
n,i,j,sum,x,k:longint;
begin
readln(n);
f[0,0]:=true;
for i:=1 to n do
begin
read(x);
for j:=sum downto 0 do
for k:=sum downto 0 do
if f[j,k] then
begin
f[j+x,k]:=true;
f[j,k+x]:=true;
end;
sum:=sum+x;
end;
for i:=sum downto 1 do
if f then
begin
writeln(i);
halt;
end;
writeln('Impossible');
end. -
0
sinbking11 LV 8 @ 2009-11-03 14:33:09
设f表示前i块水晶，两塔高度差为j时较高的那个塔的高度。
DP方程:
f=max{f,f,f+j} (j=h[i])
解析：
f 表示不放第i块水晶;
f 表示第i块水晶放到了较矮的那个塔上，而且矮塔仍然为矮塔，填补了高度差；
f+j 表示第i块水晶放到了较矮的那个塔上，但是矮塔变成了高塔；
f+h[i] 表示第i块水晶放到了较高的塔上，增加了高度差；
边界条件：
如果刚开始的f值都为0的话，调试的时候会发现，有许多不合逻辑的答案，例如:h[1]=1,f[1,2]也会算出值为1，但其实是无法用高度为1的水晶搭出高度差大于等于2的双塔的。
所以要把所先把所有的f赋成-maxlongint，然后f[0,0]:=0。
程序代码：
var
f:array[0..100,0..2000]of integer;
n,sum,i,j,k:integer;
h:array[1..100]of integer;
function max(x,y,z:integer):integer;
begin
max:=x;
if max -
0
var
b,c,d,m,n,i,j,sum:longint;
a:array[0..200] of longint;
f:array[0..200,0..20000] of longint;procedure init;
begin
read(m);
sum:=0;
for i:=1 to m do
begin
read(a[i]);
sum:=sum+a[i];
end;for i:= 0 to m do
for j:=1 to sum do f:=-maxlongint;end;
procedure main;
begin
f[0,0]:=0;
for i:=1 to m do
for j:=sum downto 0 do
begin
if f -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0msprogram ex;
var i,j,n,sum:longint;
h:array[1..100]of longint;
f:array[0..100,0..2000]of longint;procedure init;
var i,j:longint;
begin
readln(n);
for i:=1 to n do read(h[i]);
end;function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;procedure dp;
var i,j:longint;
begin
filldword(f,sizeof(f)div 4,-maxlongint);
f[0,0]:=0;
for i:=1 to n do
begin
inc(sum,h[i]);
for j:=0 to sum do
begin
if j>=h[i] then
f:=max(f,max(f,f+h[i]));
if h[i]>=j then
f:=max(f,max(f,f+j));
end;
end;
end;begin
init;
dp;
if f[n,0]0 then writeln(f[n,0]) else writeln('Impossible');
end. -
0
xiaobaibai LV 9 @ 2009-10-30 21:38:51
var
b:array [0..2000,0..2000] of boolean;
n,m,i,j,k,l,g:longint;begin
fillchar(b,sizeof(b),false);
readln(n);
l:=0;
b[0,0]:=true;
for i:=1 to n do
begin
read(g);
for j:=l downto 0 do
for k:=l downto 0 do
if b[j,k] then begin b[j+g,k]:=true;b[j,k+g]:=true;end;
l:=l+g;
end;
for j:=l downto 1 do
if b[j,j] then begin writeln(j);halt;end;
writeln('Impossible');
end. -
0
sutank2009 LV 8 @ 2009-10-25 11:19:46
DP做法：
f表示拿i个水晶搭出高低差为j的时候，较低的塔高；
f:=f; //第i块水晶不参与搭建时，还是搭出了差为j的两座塔，用了前i-1块水晶；
f:=f; // 第i块水晶参与搭建，加在较高的一座塔上，当j>=a[i]时，两座塔的高度差由j-a[i]变成了j,较低的塔的高度还是f;
f:=f+a[i]; //当第i块水晶加在较低的一座塔上时，有两种情况，要么较低的塔加高后还是没有较高的塔高，则高度差减少了a[i],低塔的高度增加了a[i];
f:=f+a[i]-j;//要么较低的塔加高后比较高的塔高一些，j -
0
sunny显示我超时4个点 可现在居然显示我AC了
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 431ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 588ms
├ 测试数据 07：运行超时...
├ 测试数据 08：运行超时...
├ 测试数据 09：运行超时...
├ 测试数据 10：运行超时...
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：60 有效耗时：1019msvar
n,i,j,k,x,ji:longint;
f:array[0..2000,0..2000]of boolean;
begin
readln(n);
fillchar(f,sizeof(f),0);
ji:=0;
f[0,0]:=true;
for i:=1 to n do
begin
read(x);
for j:=ji downto 0 do
for k:=ji downto 0 do
if f[j,k] then
begin
f[j+x,k]:=true;
f[j,k+x]:=true;
end;
ji:=ji+x;
end;
for i:=ji downto 0 do
if f then break;
if i=0 then writeln('Impossible') else writeln(i);
end.
绿色的云
LV 10
@ 2013-05-26 20:03:05
