rp算法.

7eleven真乃强吟

dp也可

{f=左边i人，右边j人,左边k滴血，（右边sum[j+i]-k滴血）}

丑了点，将就一下

for i:=1 to n do

for j:=0 to i do

if f[j,i-1-j,k]

then begin

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

f[j,i-j,k]:=true;

end;

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

感谢7eleven大牛提示

f表示：前i个人，分成两组，血值总和的差为j,血值大的一组人数减血值小的一组人数的差为k，是否可行。再用一个数组记录血值较大的一组的血值。直接Dp，就可以了。

ac=random+RP!!!!!!!!!

random+rp=ac!!

DP!随机调整貌似不能保证答案的正确性~验证完毕!

DP?

请问大牛们，随机交换至少多少次啊？？？？？

DP

将总和DIV 2，然后背包

二维数组f表示用i件物品形成j的总量能否达到，能为1否为0

方程:if f=1 then f:=1

注意i要从n div 2 downto 1

最慢的一个点150ms，其他0ms

应该还可以优化

PUPPY果然飞速

没优化DP 97ms

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

我的rp太差了！！第3组数据怎么这么好？？

我骗来数据，自己试半天没有一次是正确答案！！！只好cheat通过！！大家要BS就BS吧！！！

编译通过...

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

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

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

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

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

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

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

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

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

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

类似枚举 不用rp也可以过

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

做法同下

不用rp,用一个说不出名字但类似枚举的方法.

将数据分成两组，分别为a,b.和为sum1,sum2

然后开始枚举。

for i:=1 to l1 do

for j:=1 to l2 do

每次这样的循环只换两个数，但要保证交换后使目前的差值最小。

然后再继续循环交换，直到无法再交换为止。

即是，无法再交换使得他们的差值最小.

然后就输出。

做起来快捷方便，一下就AC了.不需要random.

random 1m次,看它还能不过...

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

看来我的RP很好.

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

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

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

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

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

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

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

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

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

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

dp AC靠Puppy,random AC靠rp.

编译通过...

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

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

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

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

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

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

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

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

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

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

简单的dp就ac了

楼下怎么都RP？

这题真的是靠RP过的.....用蒙特卡罗法,随机交换,生成随机的组合,然后取差的绝对值最小的那组输出....

朝着DP的方向想了半天也只过了2个点.....看来RP无敌!