hdu 1171 Big Event in HDU【生成函数】

按套路列生成函数式子然后暴力乘，这样复杂度看起来非常大，但是可以动态维护最大值，这样就是O(能过)的了
仔细想想这个多项式暴力乘理解成背包dp也行？

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=300005;
int n,m,a[N],b[N],v[N],w[N];
int main()
{
    while(scanf("%d",&n)&&n>0)
    {
        memset(a,sizeof(a));
        memset(b,sizeof(b));
        for(int i=1;i<=n;i++)
            scanf("%d%d",&v[i],&w[i]);
        for(int i=0;i<=v[1]*w[1];i+=v[1])
            a[i]=1;
        m=v[1]*w[1];
        for(int i=2;i<=n;i++)
        {
            for(int j=0;j<=m;j++)
                for(int k=0;k<=v[i]*w[i];k+=v[i])
                    b[j+k]+=a[j];
            m+=v[i]*w[i];
            for(int i=0;i<=m;i++)
                a[i]=b[i],b[i]=0;
        }
        for(int i=m/2;i>=0;i--)
            if(a[i])
            {
                printf("%d %dn",m-i,i);
                break;
            }
    }
    return 0;
}