学步园

母函数的应用，和一般母函数不同的是：这个是求天枰根据所给的不同砝码，天枰不能称出的重量。我们求出天枰能称出的不同质量，就可以知道在砝码的质量总和中所不能称出的质量了。先用一般的母函数方法求出能砝码只放一边所能称出的质量，然后，逐渐用它一边能表示出的质量较大的逐个减去质量较小的砝码，就能求出所有能表示的质量。 求出所有能表达的质量，那么不能表达的质量也就迎刃而解了。

#include<iostream><br /> #include<algorithm><br /> using namespace std;<br /> int c1[10100];<br /> int c2[10100];<br /> int b[10100];<br /> int main()<br /> {<br /> int a[110];<br /> int n,i,j,k,sum,t;</p> <p> while(scanf("%d",&n)!=EOF)<br /> {<br /> sum=0;<br /> for(i=0;i<n;i++)<br /> {<br /> scanf("%d",&a[i]);<br /> sum+=a[i];<br /> }<br /> sort(a,a+n);<br /> memset(c1,0,sizeof(c1));<br /> memset(c2,0,sizeof(c2));<br /> c1[0]=c1[a[0]]=1;<br /> for(i=1;i<n;i++)<br /> {<br /> for(j=0;j<=sum;j++)<br /> {<br /> for(k=0;k+j<=sum&&k<=a[i];k+=a[i])<br /> c2[k+j]+=c1[j];<br /> }<br /> for(j=0;j<=sum;j++)<br /> {<br /> c1[j]=c2[j];<br /> c2[j]=0;<br /> }<br /> }<br /> for(i=sum;i>=2;i--)<br /> {<br /> if(c1[i]==0)continue;<br /> for(j=1;j<i;j++)<br /> {<br /> if(c1[j]==0)continue;<br /> c2[i-j]=1;</p> <p> }<br /> }<br /> k=0;<br /> //for(i=0;i<=sum;i++)<br /> //printf("%d:%d ",c1[i],c2[i]);<br /> for(i=0;i<=sum;i++)<br /> {<br /> if(c1[i]==0&&c2[i]==0)b[k++]=i;<br /> }<br /> printf("%d/n",k);<br /> for(i=0;i<k;i++)<br /> printf(i<k-1?"%d ":"%d/n",b[i]);<br /> }<br /> return 0;<br /> }</p> <p>