测试数据 #0: Accepted, time = 0 ms, mem = 772 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 772 KiB, score = 10
测试数据 #2: Accepted, time = 3 ms, mem = 772 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 768 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 772 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 772 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 768 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 772 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 768 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 772 KiB, score = 10

var
cat:array[1..200]of longint;
g1,g2:array[1..100]of longint;
group1,group2,n,cat1,cat2,i,cha,x,y:longint;
begin
readln(n);
for i:=1 to n div 2 do
begin
readln(cat[i]);
group1:=group1+cat[i];
g1[i]:=i;
end;
for i:=(n div 2)+1 to n do
begin
readln(cat[i]);
group2:=group2+cat[i];
g2[i-(n div 2)]:=i;
end;
cha:=abs(group1-group2);
for cat1:=1 to n div 2 do
for cat2:=n div 2+1 to n do
begin
if abs((group1-cat[g1[cat1]]+cat[g2[cat2-(n div 2)]])-(group2-cat[g2[cat2-(n div 2)]]+cat[g1[cat1]]))<cha then
begin
cha:=abs((group1-cat[g1[cat1]]+cat[g2[cat2-(n div 2)]])-(group2-cat[g2[cat2-(n div 2)]]+cat[g1[cat1]]));
x:=group1-cat[g1[cat1]]+cat[g2[cat2-(n div 2)]];
y:=group2-cat[g2[cat2-(n div 2)]]+cat[g1[cat1]];
group1:=x; group2:=y;
i:=g1[cat1];
g1[cat1]:=g2[cat2-(n div 2)];
g2[cat2-(n div 2)]:=i;
end;
end;
if group1<group2 then writeln(group1,' ',group2) else writeln(group2,' ',group1);
end.

理解错题意害死人啊！大家一定要认真读题!我还以为可以不选某些士兵，结果想了半天写个四维动归，才发现，原来所有士兵都要选！那么就是很明显的背包啊！

一定要认真读题啊！

一定要认真读题啊！

一定要认真读题啊！

一定要认真读题啊！

一定要认真读题啊！

一定要认真读题啊！

数据范围真实际 哈哈

两部分的兵最多只能差一个。。。。。这好恶心啊。。

这只是一个背包。。 稍微处理一下就可以了

晕了半天没想出DP

写了个随机调整 90分。。。。

用7eleven的做法A得冷easy

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

因为血量只有1..40.不过40种

因此最优解的数量非常多.随机化算法是可行的.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

注意循环顺序和，n=奇数的情况。。。

还有就是不要在VJ评测机上卡太严重的时候交题，否则TLE or 编译失败……

数组开小了判的是超时，我的AC率...

DP，背包的变种，注意要倒序

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

用DP

lx的 因为你太贪了，所以比最优解优

编译通过...

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

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

　├ 错误行输出 40 4...

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

　├ 错误行输出 361 36...

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

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

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

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

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

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

　├ 错误行输出 122 1...

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

var n,i,aa,bb:longint;

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

procedure qsort(l,r:longint);

var i,j,temp,mid:longint;

begin

i:=l;

j:=r;

mid:=a[(i+j) div 2];

repeat

while a[i]mid do dec(j);

if (ij;

if (il) then qsort(l,j);

end;

begin

readln(n);

for i:=1 to n do

readln(a[i]);

qsort(1,n);

aa:=0;bb:=0;

for i:=n downto 1 do

if (aa>bb) then bb:=bb+a[i]

else aa:=aa+a[i];

if (aa>bb) then writeln(bb,' ',aa)

else writeln(aa,' ',bb);

end.

小弟不会随机化，DP也不熟，就贪了一下......

可是？

输出是小的在前面，那看上面的数据，我的解貌似比标准输出更优？

麻烦哪位为小弟解惑，小弟不胜感激...

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

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

　├ 错误行输出

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

　├ 错误行输出

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

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

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

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

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

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

　├ 错误行输出

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

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

Unaccepted 有效得分：70 有效耗时：1122ms

f表示i的血量是否可以由j个兵来达到

但是如果是普通的DP会TLE两个点

程序中我用了一个tot2和index[]

tot2表示现在最多达到的血量 index[i]表示i的血量最多多少人达到

这样程序速度就秒出了

program vijos1153;

var n,i,j,k,sum,x,y,p,q,min:longint;

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

　　f:array[0..5000,0..200] of longint;

begin

readln(n);

for i:=1 to N do begin

　　readln(a[i]);

　　sum:=sum+a[i];

end;

fillchar(f,sizeof(f),0);

f[0,0]:=1;

for i:=1 to N do begin

　　for j:=sum div 2+100-a[i] downto 0 do

　　 for k:=0 to N-1 do

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

end;

if N mod 2=0 then begin x:=N div 2; y:=N div 2; end;

if N mod 2=1 then begin x:=N div 2; y:=N div 2+1; end;

for i:=sum div 2 to sum do

　　if (f=1) or (f=1) then

　　 begin min:=abs(i-(sum-i)); p:=i; break; end;

for i:=sum div 2-1 downto 1 do begin

　　if abs(i-(sum-i))>min then break;

　　if ((f=1) or (f=1)) and (abs(i-(sum-i))

用记忆化搜索可以全0 MS.

f表示用i个人，j的血能否到达。(boolean 或 枚举类型)

f=f[i-1,j-a[k]]or f

当递归到f=true 时k就可以(break)终止循环了。

但是要穷举递归f[n >> 1,i], 0 1,当f[n >> 1,i]=true 时输出并结束程序。

PS：n >> 1 = n shr 1 = n div 2

AC了7个数据，然后骗数据

这种状态方程很难想哈。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

随机了10W次