hdu 1709 The Balance (모 함수)

1395 단어 HDU
제목:http://acm.hdu.edu.cn/showproblem.php?pid=1709
조합 문제, 모 함 수 를 응용 할 때 주의해 야 할 것 은 모든 다른 분동 이 하나 밖 에 없 으 며, 더 할 수 있 고, 서로 줄 일 수 있다 는 것 이다.그래서 s (x) = (1 + x ^ a) (1 + x ^ b) (1 + x ^ c) --- (1 + x ^ z).
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[105];
int c1[10005],c2[10005],zero[10005];
int main()
{
    //freopen("cin.txt","r",stdin);
    int n,i,j,num,sum;
    while(cin>>n){
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));
        sum=0;
        for(i=0;i<n;i++){
            scanf("%d",&a[i]);
            sum+=a[i];
        }
        c1[0]=1;  c1[a[0]]=1;
        for(i=1;i<n;i++){
            for(j=0;j<=sum;j++)c2[j]+=c1[j];
            for(j=0;j<=sum;j++){
                c2[a[i]+j]+=c1[j];
                if(j>a[i])c2[j-a[i]]+=c1[j];
                if(j<a[i])c2[a[i]-j]+=c1[j];
            }
            for(j=0;j<=sum;j++){
                c1[j]=c2[j];
                c2[j]=0;
            }
        }
        int res=0;
        for(i=1;i<=sum;i++){
            if(c1[i]==0)zero[res++]=i;
        }
        printf("%d
",res); if(res){ for(i=0;i<res-1;i++)printf("%d ",zero[i]); printf("%d
",zero[res-1]); } } return 0; }

좋은 웹페이지 즐겨찾기