1557.txt

杭电acm解题报告2001---2099.

#include <cstdio>
#include <memory>
#define Max 100100
int sum,n,t,avg;
int pn[30];
int num[2][Max],*pre,*next,*pt;

inline int cal(int ig)
{
    int i,j,s,mmax=10;
    memset(num,0,sizeof(num));
    pre=num[0];next=num[1];
    for(i=0;i<n;i++)
    {
        pre[0]=1;
        if(i==ig)    continue;
        for(j=0;j<mmax;j++)
            if(pre[j])
            {
                next[j]+=pre[j];
                next[j+pn[i]]+=pre[j];
            }
            mmax += pn[i];
            pt=pre;
            pre=next;
            next=pt;
            memset(next,0,sizeof(num[0]));
    }
    s=0;
    i= avg+1>pn[ig] ? avg+1-pn[ig] : 0;
    for( ;i<=avg;i++)    s+= pre[i];
    return s;
}

int main()
{
    int i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        sum=0;
        for(i=0;i<n;i++)
            scanf("%d",&pn[i]) , sum+=pn[i];
        avg=sum/2;
        for(i=0;i<n;i++)
        {
            printf(i==0 ? "%d" : " %d",cal(i));
        }
        printf("\n");
    }
}