hdu 1028 && hdu 1398 && hdu 1085 && hdu 1171 ——生成函数

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1028

就是可以用任意个1、2、3、...，所以式子写出来就是这样：(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)...(1+x^n+x^(2*n)+...)... 因为求 x^n 系数，所以再往后的式子就没有贡献了，求到第 n 个式子即可。

一个x^2就像一条边一样，可以让第 k 项的系数转移给第 k+2 项。按这个思路写代码就行了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=125;
int n,a[N],b[N];
int main()
{
  while(scanf("%d",&n)==1)
    {
      for(int i=0;i<=n;i++)
    a[i]=1,b[i]=0;
      for(int i=2;i<=n;i++)
    {
      for(int j=0;j<=n;j++)
        for(int k=0;j+k<=n;k+=i)
          b[j+k]+=a[j];
      for(int j=0;j<=n;j++)
        a[j]=b[j],b[j]=0;
    }
      printf("%d
",a[n]);
    }
  return 0;
}

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1398

同上。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=305,M=17;
int n,a[N],b[N],w[M+5];
int main()
{
  for(int i=1;i<=M;i++)w[i]=i*i;
  while(1)
    {
      scanf("%d",&n);if(!n)return 0;
      for(int i=0;i<=n;i++)
    a[i]=1,b[i]=0;
      for(int i=2;i<=M;i++)
    {
      for(int j=0;j<=n;j++)
        for(int k=0;j+k<=n;k+=w[i])
          b[j+k]+=a[j];
      for(int j=0;j<=n;j++)
        a[j]=b[j],b[j]=0;
    }
      printf("%d
",a[n]);
    }
}

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1085

感觉不从生成函数的角度看也可以很简单。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=8005;
int n1,n2,n3;
bool a[N];
int main()
{
  while(1)
    {
      scanf("%d%d%d",&n1,&n2,&n3);
      if(!n1&&!n2&&!n3)return 0;
      int lm=n1+(n2<<1)+n3*5;
      for(int i=lm+1;i>n1;i--)a[i]=0;//lm+1
      for(int i=0;i<=n1;i++)a[i]=1;
      for(int i=n1+(n2<<1);i>n1;i--)
    {
      if(a[i])continue;
      for(int j=min(n2<<1,i-(i&1));j>0;j-=2)
        if(a[i-j]) {a[i]=1;break;}
    }
      for(int i=lm;i>n1;i--)
    {
      if(a[i])continue;
      for(int j=min(n3*5,i/5*5);j>0;j-=5)
        if(a[i-j]) {a[i]=1;break;}
    }
      for(int i=n1+1;i<=lm+1;i++)
    if(!a[i]){printf("%d
",i);break;}
    }
}

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1171

其实我就是写了一个很暴力的多重背包？

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=55,M=N*N*100;
int n,v[N],c[N];
bool a[M];
int main()
{
  a[0]=1;
  while(1)
    {
      scanf("%d",&n);if(n<0)return 0;
      int sm=0;
      for(int i=1;i<=n;i++)
    scanf("%d%d",&v[i],&c[i]),sm+=v[i]*c[i];
      for(int i=1;i<=sm;i++)a[i]=0;
      sm=0;
      for(int i=1;i<=n;i++)
    {
      sm+=v[i]*c[i];
      for(int j=sm;j>0;j--)
        {
          if(a[j])continue;
          for(int k=0;k<=c[i];k++)
        {
          if(k*v[i]>j)break;
          if(a[j-k*v[i]]){a[j]=1;break;}
        }
        }
    }
      int d=sm>>1;
      for(int i=d;i>=0;i--)
    if(a[i]){printf("%d %d
",sm-i,i);break;}
    }
}