选课时间(题目已修改,注意读题)
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1038 Accepted Submission(s): 872
Problem Description
又到了选课的时间了,xhd看着选课表发呆,为了想让下一学期好过点,他想知道学n个学分共有多少组合。你来帮帮他吧。(xhd认为一样学分的课没区别)
Input
输入数据的第一行是一个数据T,表示有T组数据。
每组数据的第一行是两个整数n(1 <= n <= 40),k(1 <= k <=。
接着有k行,每行有两个整数a(1 <= a <=,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
算法分析:此题是我做的第一个用组合数学中母函数的方法解决的题目,虽然可以用多重背包的思想做,但母函数的思想同样也不容忽视!
该题等价于:从多重集合Couse={a1*b1,a2*b2,……,ak*bk}选择元素,使其和等于n,是标准的母函数使用的例子,应熟练掌握。
#include <iostream>
#include <memory.h>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=100;
struct node
{
int value;
int cnt;
}info[maxn];
bool cmp(node a,node b)
{
return a.value<b.value;
}
int data[maxn];
int s[maxn];
int n,k;
int a,b;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(data,0,sizeof(data));
scanf("%d%d",&n,&k);
for(int i=1;i<=k;i++)
{
scanf("%d%d",&a,&b);
info[i].value=a;
info[i].cnt=b;
//data[a]=1;
}
data[0]=1;
//sort(info+1,info+k+1,cmp);
for(int i=1;i<=k;i++)
{
memset(s,0,sizeof(s));
if(info[i].value>n) break;
for(int j=0;j<=n;j++)
{
if(data[j]>0)
{
for(int r=1;r<=info[i].cnt&&j+info[i].value*r<=n;r++)
{
s[j+info[i].value*r]+=data[j];
}
}
}
for(int j=0;j<=n;j++) data[j]+=s[j];
}
printf("%d\n",data[n]);
}
return 0;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu-api 是一个集结 HDU 所有教务管理服务的 SDK,提供了一卡通服务、考试、课表、选课和一些公共信息如空闲教室、上课时间等信息的 API。 hdu-api 主要基于 Requests 库和 Beautiful Soup 库写成。 特性 支持一卡通...
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu1290 解题报告 献给杭电五十周年校庆的礼物 (切西瓜问题,即平面分割空间)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
HDU图论题目分类