hdu 1171 Big Event in HDU （母函數）

轉換為母函數的思路是：把設備排列組合，把所有可能的組合都打出來，然後從總 價值的中間開始搜，只要搜到第一個就是了，再用total-i就是最靠近的兩個價值了。。所以輸出是total-i,i。這就不用擔心總價值是奇數了。寫 出母函數的生成函數就可以快速秒掉了。

[csharp]
#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) www.2cto.com
            { 
                printf("%d %d\n",tal-i,i);break; 
            } 
        } 
    } 
    return 0; 
}