首页 > 代码库 > 选课时间!
选课时间!
选课时间(题目已修改,注意读题)
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1516 Accepted Submission(s): 1253
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门。
每组数据的第一行是两个整数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
Author
xhd
Source
ACM程序设计期末考试_热身赛(感谢 xhd & 8600)
Recommend
lcy
1 #include<stdio.h> 2 #include<string.h> 3 #define MAXN 40 4 int a[10],b[10]; 5 int c1[MAXN+10],c2[MAXN+10]; 6 int n; 7 void mufun(int k) 8 { 9 memset(c1,0,sizeof(c1));10 memset(c2,0,sizeof(c2));11 for(int i=0;i<=b[0]&&i*a[0]<=n;i++)12 c1[i*a[0]]=1;13 for(int t=1;t<k;t++)14 {15 for(int i=0;i<=n;i++)16 {17 for(int j=0;j+i<=n&&j/a[t]<=b[t];j+=a[t])18 c2[i+j]+=c1[i];19 20 } 21 for(int i=0;i<=n;i++)22 {23 c1[i]=c2[i];24 c2[i]=0;25 } 26 } 27 } 28 int main()29 {30 int T;31 scanf("%d",&T);32 int k;33 while(T--)34 {35 scanf("%d%d",&n,&k);36 for(int i=0;i<k;i++)37 scanf("%d%d",&a[i],&b[i]);38 mufun(k);39 printf("%d\n",c1[n]);40 } 41 return 0;42 }
选课时间!
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。