题解 UVA10032 【Tug of War】

yaoxiangyuan · 2021-11-07 21:24:32 · 题解

修改于 2022 2.17 ，因为之前我未注意到题目的格式要求，导致代码出现问题。

题目链接

个人认为是一个很特别的 dp，并且有背包思想。

1. 简洁题意：

把 n 个数分为两堆，一堆中有 \lfloor n/2 \rfloor 个数，另一堆中有其他的数，要求两堆数尽量接近。

2. 题目分析（位运算 + 状压）

1. 背景分析：因为 n \le 100，且即如果 n 是偶数，这两个部分均要有 n/2 块，如果 n 是奇数，则必须分为 \lfloor n/2 \rfloor 和 \lfloor n/2 \rfloor + 1 两个部分，则 m \le 50，因为 m 很小，可以考虑状压。

2. 解法内容：我们设计状态 f[i] 代表它能被几个数拼出来，该数组中存一个二进制数，它的第 j 位代表 i 这个数是否能够用 j 个数拼出来，能则为 1，不能则为 0。转移方程即为：

我们只要找到一个能被 n/2 个数拼出来的并且最接近所有数的和的一半的数，求出动态规划的 f 数组后，扫一遍统计答案即可。

3. 参考代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int T,n,a[105],s,ans1,ans2,te;
long long f[100005],t;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        s=0;//多组数据
        memset(f,0,sizeof(f));//多组数据清空
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            s+=a[i];//先求所有数的和
        }
        f[0]=1;
        t=1ll<<n/2+1;
        t--;
        te=0x3f3f3f3f;
        for(int i=0;i<n;i++){
            for(int j=s;j>=a[i];j--){
                f[j]|=((f[j-a[i]]<<1)&t);//把数值固定在t的范围内（根据题意要求）
            }
        }
        for(int i=0;i<=s;i++){
            if(f[i]&(1ll<<(n/2)))
            if(abs(i-(s-i))<te){//这里是选取相差最小的方案
                te=abs((i<<1)-s);
                ans1=i;
                ans2=s-i;
            }
            if(ans1>ans2){
                swap(ans1,ans2);//保证小的在前面
            }
        }
        printf("%d %d\n",ans1,ans2);//输出答案，记得换行
        if(T) putchar('\n');//题目格式要求
    }
    return 0;
}