HDU 1079 生成函数

Problem Description 又到了选课的时间了，xhd看着选课表发呆，为了想让下一学期好过点，他想知道学n个学分共有多少组合。你来帮帮他吧。（xhd认为一样学分的课没区别）

 

Input 输入数据的第一行是一个数据T，表示有T组数据。 每组数据的第一行是两个整数n(1 <= n <= 40)，k(1 <= k <= 8)。 接着有k行，每行有两个整数a(1 <= a <= 8),b(1 <= b <= 10)，表示学分为a的课有b门。 Output 对于每组输入数据，输出一个整数，表示学n个学分的组合数。 Sample Input 2 2 2 1 2 2 1 40 8 1 1 2 2 3 2 4 2 5 8 6 9 7 6 8 8 这是一道典型的运用母函数求解的题目！有关母函数的更多了解，在这里： http://blog.csdn.net/zhangxiang0125/archive/2011/02/10/6177930.aspx #include<cstdio> #include<algorithm> using namespace std; int main() { freopen("zx.in","r",stdin); freopen("zx.out","w",stdout); int ncase,nump,numx; int curnum[50],sumnum[50],arrp[15],arrk[15]; scanf("%d",&ncase); while(ncase--) { scanf("%d%d",&nump,&numx); memset(curnum,0,sizeof(curnum)); memset(sumnum,0,sizeof(sumnum)); for(int i=1;i<=numx;i++) scanf("%d%d",&arrp[i],&arrk[i]); for(int i=0;i<=arrp[1]*arrk[1];i+=arrp[1]) sumnum[i]=1; for(int i=2;i<=numx;i++) { for(int j=0;j<=nump;j++) { for(int k=0;k+j<=nump&&k<=arrp[i]*arrk[i];k+=arrp[i]) { curnum[k+j]+=sumnum[j]; } } for(int j=0;j<=nump;j++) { sumnum[j]=curnum[j]; curnum[j]=0; } } printf("%d/n",sumnum[nump]); } return 0; }