prob 1014 DP(动态规划)

#include <stdio.h>
#include <string.h>

int dp[120001];
int c[7];
int sum, divi;
static int solve(void);
int main(int argc, char **argv)
{
        int cases = 0, i;
        while(1){
                cases++;
                sum = divi = 0;
                memset(dp, 0, sizeof(dp));
                for(i = 1; i <= 6; i++){
                        scanf("%d", &c[i]);
                        sum += c[i] * i;
                }
                getchar();
                if(sum == 0){
                        break;
                }
                else if(sum%2 == 0){
                        sum /= 2;
                        divi = solve();
                }
                printf("Collection #%d:\n", cases);
                if(divi == 1){
                        printf("Can be divided.\n");
                }
                else if(divi == 0){
                        printf("Can't be divided.\n");
                }
                printf("\n");
        }
        return 0;
}

static int solve(void)
{
        int i, j, k, temp, max = 0;

        dp[0] = 1;
        for(i = 1; i <= 6; i++){
                if(c[i]){
                        for(j = max; j >= 0; j--){
                                if(dp[j]){
                                        temp = j;
                                        for(k = 1; k <= c[i]; k++){
                                                temp += i;
                                                dp[temp] = 1;
                                                if(temp == sum){
                                                        return 1;
                                                }
                                                if(temp > sum){
                                                        break;
                                                }
                                        }
                                        if(temp > max){
                                                max = temp;
                                        }
                                        if(max > sum){
                                                max = sum;
                                        }
                                }
                        }
                }
        }
        return 0;
}