选课时间(题目已修改,注意读题)

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4624    Accepted Submission(s): 3586 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   Sample Output 2 445

解题报告：这道题可以递归，也可以直接套母函数模板。

code:递归

#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<sstream> #include<algorithm> #include<math.h> #include<queue> #include<stack> #include<map> #include<set> using namespace std; typedef long long ll; const int maxn=10; int num[maxn],ans,n,k; void dfs(int sum,int t){ if(sum==n){ ans++; return; } if(sum>n) return; for(int i=t;i<maxn;i++){ /*学分*/ for(int j=1;j<=num[i];j++){ /*数目*/ dfs(sum+i*j,i+1); } } } int main() { // freopen("input.txt","r",stdin); int t; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&k); int a,b; memset(num,0,sizeof(num)); for(int i=0;i<k;i++){ /*注意：一样学分的课没区别*/ scanf("%d%d",&a,&b); num[a]=b;/*表示学分为a的课有b门*/ } ans=0; dfs(0,1); printf("%d\n",ans); } return 0; }

code：母函数模板

#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<sstream> #include<algorithm> #include<math.h> #include<queue> #include<stack> #include<map> #include<set> using namespace std; typedef long long ll; const int maxn =100000; int c1[maxn], c2[maxn]; /* c1表示单词组合价值为i时的数目为c1[i]; c2表示中间量，保存每一次的情况 */ int price[9],num[9];/*硬币价值和个数,数据范围取n的最大值+1;下标从1开始*/ int n;/*n种价值的硬币;n个输入数据*/ int m;/*输入数据的最大组合价值*/ int main() { // freopen("input.txt","r",stdin); int t; scanf("%d",&t); while(t--) { int s; scanf("%d%d",&s,&n); memset(price,0,sizeof(price)); memset(num,0,sizeof(num)); m=0; for(int i=1;i<=n;i++){/*对price和num初始化*/ scanf("%d%d",&price[i],&num[i]); m=m+price[i]*num[i]; } memset(c1,0,sizeof(c1)); memset(c2,0,sizeof(c2)); for(int i=0;i<=price[1]*num[1]&&i<=m;i+=price[1])/*第一个表达式(1+x+x^2+..x^n)初始化*/ c1[i]=1; for(int i=2;i<=n;i++) /*i表示第i个表达式*/ { for(int j=0;j<=m;j++)/*j表示前面i个表达式累乘后的表达式里第j个变量*/ for(int k=0;k+j<=m&&k<=price[i]*num[i];k+=price[i])/*k表示第j个的指数，指数为价值*/ c2[k+j]+=c1[j]; for(int j=0;j<=m;j++) { c1[j]=c2[j]; c2[j]=0; } } printf("%d\n",c1[s]); } return 0; }