HDU1709 The Balance，雌函数套题

HDU1709 The Balance，母函数套题

因为放在天平上，所以可以放左右两边。。。所以记得不仅可以加，还可以减。。。

/******************************************************************************* # Author : Neo Fung # Email : neosfung@gmail.com # Last modified: 2012-06-13 16:07 # Filename: acm.cpp # Description :  ******************************************************************************/#ifdef _MSC_VER#define DEBUG#define _CRT_SECURE_NO_DEPRECATE#endif#include &lt;fstream&gt;#include &lt;stdio.h&gt;#include &lt;iostream&gt;#include &lt;string.h&gt;#include &lt;string&gt;#include &lt;limits.h&gt;#include &lt;algorithm&gt;#include &lt;math.h&gt;#include &lt;numeric&gt;#include &lt;functional&gt;#include &lt;ctype.h&gt;#include &lt;map&gt;using namespace std;const int kMAX=100100;const double kEPS=10E-6;int ans[kMAX],tans[kMAX];int main(void){#ifdef DEBUG    freopen("../stdin.txt","r",stdin);  freopen("../stdout.txt","w",stdout); #endif    int n,tmp;  while(~scanf("%d",&n) && n)  {map&lt;int,int&gt; mmap;int sum=0;while(n--){scanf("%d",&tmp);mmap[tmp]++;sum+=tmp;}memset(ans,0,sizeof(ans));memset(tans,0,sizeof(tans));ans[0]=1;for(map&lt;int,int&gt;::iterator iter=mmap.begin();iter!=mmap.end();++iter){for(int j=0;j&lt;=sum;++j)if(ans[j])        {for(int k=0,remain=iter-&gt;second+1;k+j&lt;=sum && remain;k+=iter-&gt;first,--remain)          {tans[k+j]+=ans[j];            tans[abs(j-k)]+=ans[j];          }        }memcpy(ans,tans,sizeof(ans));memset(tans,0,sizeof(tans));}int cnt=0;for(int i=1;i&lt;=sum;++i)if(!ans[i])tans[cnt++]=i;printf("%d\n",cnt);for(int i=0;i&lt;cnt;++i)printf("%d%c",tans[i],i==(cnt-1)?'\n':' ');  }  return 0;}

HDU1709 The Balance雌函数套题

热点推荐