编译通过...

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

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

　├ 错误行输出

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

　├ 错误行输出

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

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

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

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

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

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

　├ 错误行输出

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

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

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

纯rp算法AC!

把数据分别放入两个数组

随机枚举两个数（每个数组一个），交换，算差值，记录，…………

重复1000000次………………

开始把题目想简单了...用最简单的装箱DP做的...只对了4个点...

懒的重写,只能用指针配合DP,无奈算法太虚,第8点超时(第6个点也800MS+)...

最终必杀--CHEAT!汗...表BS我...

贪心就可以了!!!!!

奇迹，我的O(N*N*TOTAL)居然也能过！可能是剪枝太强了吧，呵呵。

谁有 O(n*tot) 的程序啊？

怎么用Hash优化？

我的DP本应该超时的（一个 FOR 200 套一个 FOR 8000）。可居然没超时，而且只有最后一个数据用了9MS，其他都是0MS。

只是第二个数据WA了。有哪位仁兄能把第二个数据发一下的？？？

直接dp果然超时

要用hash表优化一下

#include<iostream>
#include<cstdio>
using namespace std;
int n;
int a[207];
bool dp[207][8005];
int sum;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
}
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=n/2;j>=0;j--){
for(int k=sum/2;k>=0;k--){
if(dp[j][k]==1)dp[j+1][k+a[i]]=1;
}
}
}
for(int i=sum/2;i>=0;i--){
if(dp[n/2][i]==1){
cout<<i<<" "<<sum-i;
break;
}
}
return 0;
}

bitset+滚动

编译成功

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

Accepted, time = 75 ms, mem = 772 KiB, score = 100

#include <bits/stdc++.h>
using namespace std;

bitset<8000> dp[2][105];
int a[205];
int main()
{
        int n, s = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
                scanf("%d", &a[i]);
                s += a[i];
        }
        memset(dp, 0, sizeof dp);
        int now = 1, pre = 0;
        dp[pre][0][0] = 1;
        for (int i = 1; i <= n; i++) {
                for (int j = 0; j < 105 && j <= i; j++) {
                        dp[now][j] = dp[pre][j] | (dp[pre][j-1] << a[i]);
                        //cout << i << " " << j << " " << dp[now][j] << endl;
                }
                swap(now, pre);
        }
        int ans = 0;
        for (int i = 0; i <= n; i++)
                for (int k = 0; k < s; k++)
                        if (dp[pre][i][k] && abs(n-i-i) <= 1 && abs(s-k-k) < abs(s-ans-ans))
                                ans = k;
        int ans2 = s-ans;
        if (ans > ans2) swap(ans, ans2);
        cout << ans << " " << ans2 << endl;
        return 0;
}