HDU 1059 Dividing

HDU_1059

    本来杭电上的PPT是把这个题目放到生成函数里的，但是后来怎么搞都超时，于是还是用《背包九讲》里面的二进制优化的多重背包的思路去做了。

#include<stdio.h>
#include<string.h>
#define MAXD 10
#define MAXM 60010
#define MAXX 200
int S, M, X, f[MAXM], value[MAXX], elem[20];
void prepare()
{
    int i, j, k;
    for(i = 0; i < 16; i ++)
        elem[i] = (1 << i);
}
int init()
{
    int i, j, k, n;
    X = S = 0;
    for(i = 1; i <= 6; i ++)
    {
        scanf("%d", &n);
        S += n * i;
        for(j = 0; n - elem[j + 1] + 1 > 0; j ++)
            value[X ++] = elem[j] * i;
        value[X ++] = (n - elem[j] + 1) * i;
    }
    M = S / 2;
    return S;
}
void solve()
{
    int i, j, k;
    memset(f, 0, sizeof(f[0]) * (M + 1));
    for(i = 0; i < X; i ++)
    {
        for(j = M; j >= value[i]; j --)
            if((k = f[j - value[i]] + value[i]) > f[j])
                f[j] = k;
    }
    printf("%s be divided.\n", f[M] == M ? "Can" : "Can't");
}
int main()
{
    int t = 0;
    prepare();
    while(init())
    {
        printf("Collection #%d:\n", ++ t);
        if(S & 1)
            printf("Can't be divided.\n");
        else
            solve();
        printf("\n");
    }
    return 0;
}