[ZJ] d763. 好多线段

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int s[105];
int bi[105][1005]={0},ans[1005]={0},l[105]={0},ansl;
char c[10000];
void dfs(int all,int i){
    int j;
    for(;i>=0 && s[i]>all;i--){
        ansl=max(ansl,l[i]);
        for(j=0;j<ansl;j++){
            ans[j]+=bi[i][j];
            if(ans[j]>9) ans[j+1]++,ans[j]-=10;
        }

        if(ans[ansl]) ansl++;
    }
    for(;i>0;i--)
        dfs(all-s[i],i-1);
}
int main(){
    int n,m,i,j,top,x;
    bi[0][0]=1,l[0]=1;
    for(i=1;i<=100;i++){
        l[i]=l[i-1];
        for(j=0;j<l[i];j++){
            bi[i][j]+=bi[i-1][j]*2;
            if(bi[i][j]>9) bi[i][j+1]++,bi[i][j]-=10;
        }
        if(bi[i][l[i]]) l[i]++;
    }
    while(gets(&c[1])){
        top=0;
        ansl=1;
        c[0]=' ';
        for(i=0;c[i];i++){
            if(c[i-1]==' ' && c[i]<='9' && c[i]>='0'){
                sscanf(&c[i],"%d",&x);
                s[top++]=x;
            }
        }
        memset(ans,0,sizeof(ans));
        if(top==1 && s[0]==0) break;
        sort(s,s+top);
        for(i=2;i<top;i++)
            for(j=i-1;j>0;j--)
                dfs(s[i]-s[j],j-1);
        for(i=ansl-1;i>=0;i--)
            printf("%1d",ans[i]);
        puts("");
    }
}