HDU2079 选课时间(题目已修改,注意读题)【母函数】

题目链接:

?pid=2079

题目大意:

给你各种学分的课程数,问:选课凑够N学分的情况有多少种。

给你两个整数N和K,N表示要凑够的学分数。K表示接下来K行,每行为两个整数a和b。

表示学分为a的课程有b们。求出选够N学分的方案数有多少种。

思路:

可以用母函数做,,也可以用多重背包来做。这两种做法,感觉实质上没什么区别吧。多重背包

用滚动数组优化一下也是一样的。这里用母函数来解决。这是一道母函数的模板题,关于母函

数,网上有好多资料,就不再描述了。

AC代码:

#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;int A[10];int c1[44],c2[44];int main(){int T,N,K,a,b;cin >> T;while(T–){memset(A,0,sizeof(A));cin >> N >> K;for(int i = 1; i <= K; ++i){scanf("%d%d",&a,&b);A[a] = b;}for(int i = 0; i <= N; ++i){c1[i] = 0;c2[i] = 0;}c1[0] = 1;for(int i = 1; i <= K; ++i)//k门课{for(int j = 0; j <= N; ++j){for(int k = 0; k <= A[i] && j+k*i <= N; ++k)c2[j+k*i] += c1[j];}for(int j = 0; j <= N; ++j){c1[j] = c2[j];c2[j] = 0;}}cout << c1[N] << endl;}return 0;}

只有一条路不能选择——那就是放弃的路;

HDU2079 选课时间(题目已修改,注意读题)【母函数】

相关文章:

你感兴趣的文章:

标签云: