hdu 2079 选学时间_母函数

hdu 2079 选课时间_母函数

题意：需要学够n学分，有k个情况（x学分，y个相同学分的课）

解法：套母函数模板

#include <iostream>
#include<cstdio>
using namespace std;
 
int main(int argc, char** argv) {
	int i,j,k,t,sum;
	int c1[10000],c2[10000],num[120],n,m,x[120],y[120];
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		sum=0;
		for(i=0;i<m;i++){
			scanf("%d%d",&x[i],&y[i]);
			sum+=x[i]*y[i];
		}
		for(i=0;i<=sum;i++){
			c1[i]=c2[i]=0;
		}
		c1[0]=1;
		for(i=0;i<m;i++){
			for(j=0;j<=n;j++){
				for(k=0;k<=y[i]&&x[i]*k+j<=n;k++){
					c2[x[i]*k+j]+=c1[j];
				}
			}
			for(j=0;j<=n;j++){
				c1[j]=c2[j];
				c2[j]=0;
			}
		}
		printf("%d\n",c1[n]);
	}
	return 0;
}