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

神奇

f=boolean表示一队有i个人能否达到j的血量

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

此题经典的穷举

方法完全同楼上，不过要注意卡一下时间

for j:=n div 2 downto 0 do //最多用一半的人，另一半可以用sum-j求出

for k:=40*j downto 0 do //每个兵最多40滴血

尽量减少循环次数。

program p1153(input,output);

var

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

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

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

begin

readln(n);

for i:=1 to n do begin readln(a[i]); inc(m,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:=m div 2 downto 0 do

if f[n div 2,i] then begin writeln(i,' ',m-i); break; end;

end.

很经典的背包样式题。

状态转移方程是：

if (dp[j][k]) dp[j+1][k+a[i]]=1;

dp[j][k]表示用j个数，能否达到和k；

其中枚举i，然后DP求解。

优化时j可从n/2 to 0，因为取一半数，另一半也就已知了。

输出的时候，(dp[n/2][0 ... sum/2]==1)(sum为总和)中，取得的和与sum/2最接近的输出即可。

贴一下程序吧。。。

#include

main(){

FILE *fp=fopen("P1153.in","r");

FILE *ap=fopen("P1153.out","w");

int i,j,n;

int a[201];

fscanf(fp,"%d\n",&n);

int sum=0;

char dp[201][8001];

int n2;

n2=(n+1)/2;

memset(dp,0,sizeof(dp));

for (i=1;i=0;k--){

if (k+a[i]

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

裸的DP

i要从n div 2 downto 1

这是为什么？我不用这个第10个就超时。

哪位大牛解释下。

好诡异好神奇好无敌的贪心算法！！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

7eleven真大牛!

贪心就可以了

7eleven 的办法貌似是个类贪心算法?!

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我贪心竟然过了！

做完这题我终于4星半了

这题随即把,我才随即10000次居然都能交2次A2次..

RP太好了

type

re = array[1..200] of longint;

var

i, j, k: longint;

n, m: longint;

a: re;

ans1, ans2: longint;

procedure work(a: re;n: longint);

var

i, j, k: longint;

s: array[1..2] of longint;

begin

s[1] := 0;

s[2] := 0;

while n > 0 do begin

k := random(n);

inc(s[n mod 2 + 1],a[k+1]);

a[k+1] := a[n];

dec(n);

end;

if abs(s[1]-s[2])

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

7eleven 是大牛

不用cheat，不用排序，不用RP

很简单就过了

没排序，70

排序后，90

Cheat后，100 （第3组死活过不去）

话说Random等于0ms AC 。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

orz....7eleven..

很好用!!!

还是puppy厉害！

二维费用的背包背过了 交了3次才等到puppy出现。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我发现为啥用我觉得错误的方法倒过了...

program yemao;

var n:longint;

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

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

i,j,k:longint;

s:longint;

t:longint;

begin

readln(n);

s:=0;

for i:=1 to n do

begin readln(a[i]);s:=s+a[i];end;

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

f[0,0,0]:=true;

for i:=1 to n do

for j:=i downto 0 do

for k:=s downto 0 do

f:=f or f;

if n mod 2 =0 then begin t:=maxlongint;

for j:=1 to s do

if (f[n,n div 2,j])and(abs(j-(s-j))

7eleven的方法如何证明？

卧槽泥马

要1000次