题解：P10961 划分大理石

· · 题解

题目传送门

这道题是不错的背包练习题，推荐像我这样的蒟蒻来写。

题意很明白了，在此不赘述。

思路讲解

首先一个特判：当价值总和不是偶数，直接 cout<<"Can't"。

通过观察，可以很快发现这是一道背包 DP 题，而且还是 01 背包的变式——多重背包，不过与常规模板不同的是，这里只需要判断是否可以取到即可，所以我们可以将 dp 数组定义为布尔型，dp_i 表示价值 i 能否取到。

考虑转移，可以发现，dp_i 的状态只能由 dp_{i-w_i} 转移而来（w_i 为当前枚举到的物品价值），容易发现当 dp_{i-w_i} 与 dp_i 任意一者为真，dp_i 即为真，所以可以使用或运算作为转移。

而初始状态就是 dp_0 为真。

My code

#include<bits/stdc++.h>
using namespace std;
int a[10],sum,num,w[120005],id;
bool dp[120005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    while(true){
        sum=0;
        for(int i=1;i<=6;cin>>a[i],sum+=a[i]*i,i++);//计算价值总和
        num=sum>>1,id=0;//计算出要得到的价值，因为只要总价值的一半可以取到，另一半也一定可以取得到。
        fill(dp,dp+120005,false);//初始化。
        if(sum==0)break;//若价值为0，即输入均为0。
        if(sum&1)//特判。
            cout<<"Can't\n"; 
        else{
            for(int i=1;i<=6;i++)
                for(int j=1;j<=a[i];j++)w[++id]=i;//预处理w数组。
            dp[0]=true;//初始状态。
            for(int i=1;i<=id;i++)
                for(int j=num;j>=w[i];j--)
                    dp[j]|=dp[j-w[i]];//背包模板，转移使用|运算（或）。
            if(dp[num])cout<<"Can\n";
            else cout<<"Can't\n";//输出。
        }
    }
    return 0;//华丽结束。
}

但是，当你提交上去之后会惊讶的发现：

Subtask 2 全 TLE 了！！

那怎么办呢？这时候就要用二进制优化大法了！！（dalao 们可以用状态压缩。）

优化原理：

我们知道，任意一个数都可以表示为二进制数。

那换句话说，是不是二进制可以构成任意数？

所以，我们可以将一个数使用二进制各位权值之和表示，存进 w 数组里，这样就可以减少枚举的次数，于是就不会超时了！！！

AC code

#include<bits/stdc++.h>
using namespace std;
int a[10],sum,num,w[120005],id;
bool dp[120005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    while(true){
        sum=0;
        fill(dp,dp+120005,false);
        for(int i=1;i<=6;cin>>a[i],sum+=a[i]*i,i++);
        if(sum==0)break;
        num=sum>>1,id=0;
        if(sum&1){
            cout<<"Can't\n";
            continue;
        }
        for(int i=1;i<=6;i++){
            int temp=0;
            for(int j=1;(j<<1)<=a[i];j<<=1)w[++id]=i*j,temp+=j;//二进制优化。
            w[++id]=i*(a[i]-temp);//万一有剩余的，再存进去。
        }
        dp[0]=true;
        for(int i=1;i<=id;i++)
            for(int j=num;j>=w[i];j--)
            dp[j]|=dp[j-w[i]];
        if(dp[num])cout<<"Can\n";
        else cout<<"Can't\n";
    }//其他同上。
    return 0;
}