题解 - Vijos

0

graylucky LV 10 @ 2009-07-17 08:53:50

第10个点..WA了一次..

数组要开大..!

0

ufo172849z LV 10 @ 2009-07-15 16:00:39

一开始以为只要开到40的就可以了。交上去WA了一个点。

自己测了数据

5

40 1 2 3 4

终于知道了错误。把数组开到500。就AC了。不必开到4000。

0

527971925 LV 10 @ 2009-07-31 11:06:20

侥幸通过，感谢给位大牛指点！

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

李肥888 LV 10 @ 2009-07-10 09:25:13

最后三个点真是特别。。。。。。。。。

0

chlo_crys LV 7 @ 2009-05-31 14:23:55

动态规划就可以呀,写对了根本不会超时...

什么随机....不知所云...

0

qyjubriskxp LV 10 @ 2009-05-29 01:01:19

我偏不用bool数组，f(n,m,v)表示前n个物体取m个最大血值为v时与v相差的最小血值，再加动态数组优化，虽然丑陋，好歹ac了

0

pas4 LV 8 @ 2009-05-26 12:37:52

moon!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

0

asd136912 LV 8 @ 2009-06-11 13:21:42

f表示I个数，是否达到J

0

sailingfans LV 9 @ 2009-04-15 20:19:55

var

f :array[0..201,0..4000]of boolean;

health :array[1..400]of longint;

n,k,i,ii,j,tot,res,halfhealth :longint;

begin

readln(n);tot:=0;

for i:=1 to n do begin readln(health[i]);tot:=tot+health[i];end;

k:=n div 2;

halfhealth:=tot div 2;

if n mod 2=1 then k:=k+1;

fillchar(f,sizeof(f),false);

f[0,0]:=true;

for i:=1 to n do

for ii:=k-1 downto 0 do

for j:=halfhealth-health[i] downto 0 do

if f[ii,j] then f[ii+1,j+health[i]]:=true;

for i:=halfhealth downto 0 do

if f[k,i] then begin res:=i;break;end;

if n mod 2=1 then

for i:=halfhealth downto 0 do

if f[k-1,i] then begin

if i>res then res:=i;

break;

end;

writeln(res,' ',tot-res);

end.

好水，。。。。。。

0

pplong LV 8 @ 2009-04-15 13:51:38

DP 怎么做啊？？

我用的随机化算法....

时间有点长...

0

yxy LV 10 @ 2009-04-06 11:16:04

n个数中取n/2个数，使sum×2-tot最小

采用7eleven的方法交换即可（看似贪心，但是实际上每种情况都考虑到了）

其实这题动归真的很烦

0

king465659 LV 8 @ 2009-03-28 16:34:09

检查一下。谢谢。

编译通过...

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

├ 测试数据 02：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 03：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 04：答案错误...　├ 标准行输出

　├ 错误行输出

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

├ 测试数据 06：答案错误...　├ 标准行输出

　├ 错误行输出

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

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

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

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

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

Unaccepted 有效得分：60 有效耗时：0ms

program P1153;

var

a :array[1..200]of longint;

n,m,i,j,k :longint;

tot,b1,b2,c :longint;

ans :array[0..100,0..200]of longint;

begin

fillchar(ans,sizeof(ans),255);

readln(n);

for i:=0 to n do ans[0,i]:=0;

for i:=1 to n do

begin

readln(a[i]);

tot:=tot+a[i];

end;

m:=n div 2;

for i:=1 to m do

for j:=i-1 to n do

if ans-1 then

begin

for k:=j+1 to n do

ans:=ans+a[k];

end;

c:=maxlongint;

for i:=m to n do

if (ans[m,i]-1) and (c>abs(tot-ans[m,i]-ans[m,i])) then

begin

if ans[m,i]>=tot-ans[m,i] then begin b1:=tot-ans[m,i]; b2:=ans[m,i]; end else begin b1:=ans[m,i]; b2:=tot-ans[m,i]; end;

c:=abs(tot-ans[m,i]-ans[m,i]);

end;

writeln(b1,' ',b2);

end.

0

king465656 LV 8 @ 2009-03-27 19:43:36

那位大妞给我检查仪为甚麽错了。谢谢。

编译通过...

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

├ 测试数据 02：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 03：答案错误...　├ 标准行输出

　├ 错误行输出

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

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

├ 测试数据 06：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 07：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 08：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 09：运行时错误...| 错误号: 216 | 存取非法

├ 测试数据 10：运行时错误...| 错误号: 216 | 存取非法

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

Unaccepted 有效得分：30 有效耗时：0ms

program P1153;

var

a :array[1..200]of longint;

n,m,i,j,k :longint;

tot,b1,b2,c :longint;

ans :array[0..100,0..4000]of boolean;

begin

fillchar(ans,sizeof(ans),false);

readln(n);

for i:=0 to n do ans:=true;

for i:=1 to n do

begin

readln(a[i]);

tot:=tot+a[i];

end;

//if n mod 2=1 then m:=n div 2+1 else m:=n div 2;

m:=n div 2;

for i:=1 to n do

for j:=1 to m do

for k:=tot div 2 downto a[i] do

if ans[j-1,k-a[i]] then begin ans[j,k]:=true; ans[j,k-a[i]]:=true; end;

c:=maxlongint;

for i:=tot downto 1 do

if ans[m,i] then

if abs(tot-i-i)=tot-i then begin b1:=tot-i; b2:=i; end else begin b1:=i; b2:=tot-i; end;

c:=abs(tot-i-i);

end;

writeln(b1,' ',b2);

end.

0

Jollwish LV 7 @ 2009-02-28 21:48:08

简单的DP哈

0

dzs999 LV 8 @ 2009-02-25 13:09:00

program Dzs;

var

a,b,c,d,i,j,m,n,k:longint;

e:array[0..40000]of boolean;

q:array[0..40000,0..101]of boolean;

w:array[1..200]of longint;

begin

readln(n);

a:=n div 2;

for i:=1 to n do

begin

readln(w[i]);

inc(m,w[i]);

end;

b:=m div 2;

q[0,0]:=true;e[0]:=true;

for i:=1 to n do

for j:=b-w[i] downto 0 do

if e[j] then

begin

c:=j+w[i];

e[c]:=true;

for k:=a downto 0 do

if q[j,k] then q[c,k+1]:=true;

end;

if n mod 2=0 then c:=a else c:=a+1;

while (not e)or(not q)and(not q) do

dec(b);

writeln(b,' ',m-b);

end.

0

SAMTZST LV 8 @ 2009-02-21 20:19:32

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

最后三组特殊一点的……

0

inter LV 10 @ 2009-01-31 14:37:42

0

张厚 LV 3 @ 2009-01-20 19:40:58

var

n,sum,i,j,k:longint;

a:array[1..200]of longint;

f:array[0..200,0..8000]of boolean;

begin

readln(n);

sum:=0;

for i:=1 to n do

begin

read(a[i]);

inc(sum,a[i]);

end;

f[0,0]:=true;

for i:=1 to n do

for j:=n div 2 downto 0 do

for k:=40*j downto 0 do

if f[j,k] then

f[J+1,K+a[i]]:=true;

for i:=sum div 2 downto 0 do

if f[n div 2,i]

then

begin

write(i,' ',sum-i);

exit;

end;

end.

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈

0

beakham LV 8 @ 2008-12-29 11:54:35

var

n,i,j,k,tot,min:longint;

a:array[1..200]of longint;

f:array[0..201,0..8000]of boolean;

begin

readln(n);

for i:=1to n do

begin

readln(a[i]);

inc(tot,a[i]);

end;

f[0,0]:=true;

for k:=1to n do

for i:=n shr 1 downto 1do

for j:=tot downto a[k]do

if f[i-1,j-a[k]] then f:=true;

min:=51314520;

for i:=tot downto 1do

if (abs(i-tot shr 1)

0

xiaoX LV 10 @ 2008-12-18 21:30:24

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

n*（n/2）*血量加点优化 ……

把个 downto 写成 to 还过了 7组…… 无语……

感觉有点像判断背包啊……

program maogoudazhan;

var a,b:array[0..200]of integer;

f:array[0..200,-40..8000]of boolean;

i,j,k,l,m,n,x,y:integer;

begin

readln(n);

m:=0;

for i:=1 to n do

begin

read(a[i]);

m:=m+a[i];

b[i]:=m;

end;

l:=n div 2;

for i:=0 to l do

for j:=-40 to m do f:=false;

f[0,0]:=true;

for i:=1 to n do

begin

if i

题解

191 条题解

猫狗大战

信息

状态

开发

支持

题解

191 条题解

猫狗大战

信息

状态

开发

支持

还没有账户？

登录