10年9月17号Update…
状态压缩BFS 40行水过.. 代码是POJ2362的, 一样的题.. 原来本文只有1011

#include <stdio.h>

bool dfs(int a[],int u,int n,int __s,int start)
{
    if (start==n)
        return true;
    for(int i=(1<<start);i<(1<<n);i+=(2<<start)) {
        if(i&u)
            continue;
        int count=0;
        for(int j=0;j<n;j++)
            count+=a[j]*((i>>j)&1);
        if(count!=__s)
            continue;

        int __u=u|i;
        int j;
        for(j=0;j<n && ((__u>>j)&1);j++);
        if(dfs(a,__u,n,__s,j)) {
            /* DEBUG
            for(int k=0;k<n;k++)
                if((i>>k)&1)
                    printf("%d ",a[k]);
            printf("\n");   */
            return true;
        }
    }
    return false;
}


int main()
{
    int N;
    scanf("%d",&N);
    while (N--)
    {
        int n,a[21],count=0;
        scanf("%d",&n);
        for (int i=0;i<n;i++)
        {
            scanf("%d",a+i);
            count+=a[i];
        }
        printf("%s\n",count%4?"no":(dfs(a,0,n,count/4,0)?"yes":"no"));
    }
    return 0;
}

下面是一年前的垃圾代码.. 1011

#include <cstdio>
#include <cstdlib>

typedef struct part {
    int l,n;
    int who[65],used; ///How many does level[i] use; how many are used totally.
} Part;
Part a[65];
int l,n,m;  ///m records the amount of different lenths of sticks.
int myCompare(const void *a,const void *b) {
    return ((Part *)b)->l-((Part *)a)->l;
}

int next(int lv,int rem) {
    int i,j,r;
    while(1) {
        for(i=m;i>=1;i--)
            if(a[i].who[lv]>0)
                break;
        if(i==0)
            return -1;
        a[i].who[lv]--;
        a[i].used--;
        rem+=a[i].l;
        if(i==m)
            continue;
        for(j=i+1;j<=m;j++) {
            r=a[j].n-a[j].used;
            r=r<(rem/a[j].l)?r:rem/a[j].l;
            a[j].who[lv]+=r;
            a[j].used+=r;
            rem-=r*a[j].l;
        }
        return rem;
    }
}

bool vip_next(int lv1,int lv2,int s) {
    int rem=0;    ///lenths remained
    int i,r;
    bool lv1bigger=false;
    if(lv1!=lv2) {
        rem=l;
        for(i=0;i<=m;i++) {
            r=a[i].n-a[i].used;
            r=r<(rem/a[i].l)?r:rem/a[i].l;
            if(r<a[i].who[lv1])
                lv1bigger=true;
            else
                if(!lv1bigger)
                    r=a[i].who[lv1];
            a[i].used+=r;
            a[i].who[lv2]=r;
            rem-=r*a[i].l;
            if(!rem)
                break;
        }
    }
    else
        rem=next(lv2,rem);
    while(1) {
        if(a[s].who[lv2]==0) {
            for(i=s+1;i<=m;i++) {
                a[i].used-=a[i].who[lv2];
                a[i].who[lv2]=0;
            }
            return false;
        }
        if(rem==-1)
            return false;
        if(rem==0)
            return true;
        rem=next(lv2,rem);
    }
}

bool combine(int level) {
    int i,s;      ///s is which Part this level should start searching from
    if(level>n)
        return true;
    for(s=0;s<=m;s++)
        if(a[s].used!=a[s].n)
            break;
    for(i=0;i<=m;i++)
        if(a[i].used+a[i].who[level-1]>a[i].n) {
            if(!vip_next(level-1,level,s))
                return false;
            break;
        }
    if(i==m+1)
        for(i=0;i<=m;i++)
            a[i].used+=a[i].who[level]=a[i].who[level-1];
    while(1) {  ///At this point, this level's combination is ok.
        if(combine(level+1))
            return true;
        if(!vip_next(level,level,s))
            return false;
    }
}

int main() {
    int i,j,temp,count;
    while(1) {
        m=0;
        for(i=0;i<65;i++)
            a[i].used=a[i].n=0;
        scanf("%d",&n);
        if(!n)
            return 0;
        count=0;
        for(i=1;i<=n;i++) {
            scanf("%d",&temp);
            for(j=1;j<=m;j++)
                if(a[j].l==temp) {
                    a[j].n++;
                    break;
                }
            if(j>m) {
                m++;
                a[m].l=temp;
                a[m].n++;
            }
            count+=temp;
        }
        ///Initialize
        qsort(a+1,m,sizeof(Part),myCompare);
        a[0].n=1;
        a[0].who[0]=1;
        a[0].used=1;

        for(l=a[1].l;l<=count;l++) {
            n=count/l;
            a[0].l=l;
            for(i=1;i<=m;i++) {
                a[i].used=0;
                for(j=1;j<=n;j++)
                    a[i].who[j]=0;
            }
            if(count%l)
                continue;
            if(combine(1)) {
                printf("%d\n",l);
                break;
            }
        }
        /*
        for(j=1;j<=5;j++) {
            printf("\nlevel %d use ",j);
            for(i=1;i<=m;i++) {
                    printf(" %d (*%d)\n",a[i].l,a[i].who[j]);
            }
        }*/
    }
}