题解：P10961 划分大理石

ycy1124 · 2024-09-26 15:41:23 · 题解

题意

有 a_1,a_2,a_3,a_4,a_5,a_6 块大小分别为 1,2,3,4,5,6 的砖，问能否将其分成两部分并且大小之和相等。

思路

设总大小为 sum，那么只要能取出 sum \div 2 大小的就一定可以，假如 sum 不是偶数就可以直接输出 Can't 了。

对于 sum 是偶数的，先将 a_1,a_2,a_3,a_4,a_5,a_6 二进制拆分（拆分后一定可以反过来凑出 1 \sim a_i 之间所有的整数，证明很简单，这里就不证了），然后直接 01 背包就可以了。这里的 dp_i 表示的是取出大小之和为 i 的方案是否存在，最初时 dp_0=1。转移方程也很好想 dp_i 明显只能由 dp_{i-w_j} 得到（1 \le j \le tot 且 w_j \le i），w_j 表示的是第 j 个物品的价值，tot 表示的是物品总数。

代码

#include<bits/stdc++.h>
using namespace std;
int a[7];
int w[20001];
bool dp[210001];
int main(){
    int tot;
    while(scanf("%d%d%d%d%d%d",&a[1],&a[2],&a[3],&a[4],&a[5],&a[6])){
        if((a[1]+a[3]+a[5])%2!=0){//不是偶数就直接输出Can't
            printf("Can't\n");
            continue;
        }
        memset(dp,0,sizeof(dp));//多测清空
        tot=0;
        if(a[1]==0&&a[2]==0&&a[3]==0&&a[4]==0&&a[5]==0&&a[6]==0){
            return 0;
        }
        int js=(a[1]+a[2]*2+a[3]*3+a[4]*4+a[5]*5+a[6]*6)/2;//计算sum/2
        for(int i=1;i<=6;i++){
            int base=1;
            while(base<=a[i]){//二进制拆分
                a[i]-=base;
                w[++tot]=base*i;//体积和价值也等比例放大
                base*=2;
            }
            if(a[i]!=0){//这里别忘记把多余的加进去
                w[++tot]=a[i]*i;
            }
        }
        dp[0]=1;
        for(int i=1;i<=tot;i++){//完全背包
            for(int j=js;j>=w[i];j--){//遍历顺序别反了
                if(dp[j-w[i]]){
                    dp[j]=1;
                }
            }
        }
        if(dp[js]){//假如sum/2可以
            printf("Can\n");
        }
        else{
            printf("Can't\n");
        }
    }
    return 0;
}

AC 记录。