HDU 1059 Dividing

题目大意：有六堆石头，第i堆的价值为i，读入数据表示该堆石头的个数，现在要求得出是否可以分为价值相同的两堆。

题解：直接将石子数相加，如果为奇数则显然不可分，然后就是01背包的二进制拆分问题了。

#include <cstdio>
int main()
{
    int a[7],k,cnt=1;
    bool f[120000];
    while(true)
    {
        int sum=0;
        for(int i=1;i<=6;i++)
        {
            scanf("%d",&a[i]);
            sum += i * a[i];
        }
        if(sum == 0)
            break;
        printf("Collection #%d:
",cnt++);
        if(sum % 2 != 0)
        {
            printf("Can't be divided.

");
            continue;
        }
        sum /= 2;
        for(int i = sum;i > 0;i--)
            f[i] = false;
        f[0] = true;
        for(int i=1;i<=6;i++)
        {
            int t=a[i];
            for(k=1;k<=t;k<<=1)
            {
                int temp=k*i;
                for(int j=sum;j>=temp;j--)
                f[j]=f[j]||f[j-temp];
                t-=k;
            }
            if(t){
                int temp=t*i;
                for(int j=sum;j>=temp;j--)f[j]=f[j]||f[j-temp];
            }
        }
        if(f[sum])
            printf("Can be divided.

");
        else
            printf("Can't be divided.

");
    }
}