首页 > 代码库 > HDU 2079-选课时间(母函数)
HDU 2079-选课时间(母函数)
选课时间(题目已修改,注意读题)
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2996 Accepted Submission(s): 2347
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再水一发。。睡觉觉~#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <cctype> #include <cmath> #include <cstdlib> #include <vector> #include <queue> #include <set> #include <map> #include <list> #define maxn 250 #define ll long long #define INF 0x3f3f3f3f #define pp pair<int,int> using namespace std; int a[maxn],b[maxn],v[10],p,num[10],n; void solve() { memset(a,0,sizeof(a)); a[0]=1; for(int i=0;i<n;i++) { memset(b,0,sizeof(b)); for(int j=0;j<=num[i]&&j*v[i]<=p;j++) for(int k=0;k+j*v[i]<=p;k++) b[k+j*v[i]]+=a[k]; memcpy(a,b,sizeof(b)); } printf("%d\n",a[p]); } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&p,&n); for(int i=0;i<n;i++) scanf("%d%d",&v[i],&num[i]); solve(); } return 0; }
HDU 2079-选课时间(母函数)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。