HDOJ1059(多重部分和问题)

#include<cstdio>
#include<cstring>
using namespace std;
const int SIZE=120000+16;
int a[6];
int dp[SIZE];
bool check()
{
    for(int i=0;i<6;i++)
        if(a[i]!=0)
            return true;
    return false;
}
int sum;

int main()
{
    int t=0;
    while(true)
    {
        sum=0;
        for(int i=0;i<6;i++)
        {
            scanf("%d",&a[i]);
            sum+=(i+1)*a[i];
        }
        if(!check())
            break;    
        
        printf("Collection #%d:\n",++t);    
        if(sum%2==1)
        {
            printf("Can‘t be divided.\n");
        }
        else
        {
            memset(dp,-1,sizeof(dp));
            int k=sum/2;
            dp[0]=0;
            for(int i=0;i<6;i++)
            {    
                for(int j=0;j<=k;j++)
                {
                    if(dp[j]>=0)
                    {
                        dp[j]=a[i];
                    }
                    else if(j<(i+1)||dp[j-(i+1)]<=0)
                    {
                        dp[j]=-1;    
                    }
                    else
                    {
                        dp[j]=dp[j-(i+1)]-1;
                    }            
                }
            }
            if(dp[k]>=0)
            {
                printf("Can be divided.\n");
            }
            else
            {
                printf("Can‘t be divided.\n");
            }
        }
        printf("\n");
    }
    return 0;
}