acwing318 划分大理石

有价值分别为 1..6 的大理石各 a[1..6]

块，现要将它们分成两部分，使得两部分价值之和相等，问是否可以实现。

其中大理石的总数不超过 20000

。

输入格式

输入包含多组数据！

每组数据占一行，包含 6

。

当输入为 0 0 0 0 0 0 时表示输入结束，且该行无需考虑。

输出格式

每组数据输出一个结果，每个结果占一行。

如果可以实现则输出 Can，否则输出 Can't。

输入样例：

4 7 4 5 9 1
9 8 1 7 2 4
6 6 8 5 9 2
1 6 6 1 0 7
5 9 3 8 8 4
0 0 0 0 0 0

输出样例：

Can't
Can
Can't
Can't
Can 

这题还是比较好写的
我最开始的时候都没看出来这是一个背包
先说说我想到的第一个思路吧
设f[a1][a2][a3][a4][a5][a6]表示在用了a1个1，a2个2·····a6个6的时候是否有可能能够划分为价值相等的两部分
转移就是尝试同时增加两部分价值相等的大理石，距离就是分解数字
比如6=3+3=3+2+1=4+2=2+2+2·····
很多，但是因为只到了6，就能够用类似打表的办法做出来
复杂度应该是O(a[1]*a[2]····*a[6])
直接爆炸
（可能是没睡好脑子不清醒吧。。想出了这么炸裂的做法）

正解

我们只要能够从这些石头里面选出来总价值为sum/2的组合，那就说明这些大理石肯定能够被成功划分（sum是所有大理石的价值和）
所以这就是一个可行性多重背包。。而且因为只有6种，复杂度降低了。。。
就是poj1742coins这题的弱化版
思路一模一样，既然我们已经不关心“最优解”而只关心“可行性”，那那些已知可行的状态自然是没有再转移过去的必要，硬币的数量也不需要浪费在这些情况上面了

感觉在写一次这种题目，有了些新的感受
这种转移的方式其实是为了这种题目专门设计的。。
而并不只是一个简单的改版
积累积累

code

     #include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read() {
    char c=getchar();int a=0,b=1;
    for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
    for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b;
}
bool  f[120001];int a[7],used[120001];
int main()
{
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    while(1)
    {
        int sum=0;
        memset(f,0,sizeof(f));
        for(int i=1;i<=6;i++)
        {
            a[i]=read();
            sum+=a[i]*i;
        }
        if(sum==0)return 0;
        if(sum%2)
        {
            cout<<"Can't"<<endl;
        }
        else
        {
            f[0]=1;
            for(int i=1;i<=6;i++)
            {
                memset(used,0,sizeof(used));
                for(int j=0;j<=sum/2;j++)
                {
                    if(f[j]&&!f[j+i]&&used[j]<a[i])
                    {
                        f[j+i]=1;
                        used[j+i]=used[j]+1;
                    }
                }
            }
//            for(int i=1;i<=sum/2;i++)cout<<f[i]<<' ';
//            cout<<endl;
            if(f[sum/2])cout<<"Can"<<endl;
            else cout<<"Can't"<<endl;
        }
    }
    return 0;
}