hdu 1171 Big Event in HDU （母函数）

点击打开链接

转换为母函数的思路是：把设备排列组合，把所有可能的组合都打出来，然后从总 价值的中间开始搜，只要搜到第一个就是了，再用total-i就是最靠近的两个价值了。。所以输出是total-i,i。这就不用担心总价值是奇数了。写 出母函数的生成函数就可以快速秒掉了。

#include"stdio.h"#include"stdlib.h"#include"string.h"struct node{int v,m,sum;}aa[250008];int c1[250008],c2[250008];int main(){int n,i,j,k,tal;while(scanf("%d",&n)!=EOF){if(n<0)break;tal=0;memset(c1,0,sizeof(c1));memset(c2,0,sizeof(c2));for(i=1;i<=n;i++){scanf("%d%d",&aa[i].v,&aa[i].m);aa[i].sum=aa[i].m*aa[i].v;tal+=aa[i].sum;}c1[0]=1;for(i=aa[1].v;i<=aa[1].sum;i+=aa[1].v)c1[i]=1;for(i=2;i<=n;i++){for(j=0;j<=tal;j++){for(k=0;k+j<=tal&&k<=aa[i].sum;k+=aa[i].v)c2[j+k]+=c1[j];}for(j=0;j<=tal;j++){c1[j]=c2[j];c2[j]=0;}}for(i=tal/2;i>=0;i--){if(c1[i]!=0){printf("%d %d\n",tal-i,i);break;}}}return 0;}