首页 > 代码库 > hdu 2079 选课时间(题目已修改,注意读题)

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

2024-08-05 22:43:05   213人阅读

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

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3031    Accepted Submission(s): 2372


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
题目大意：给定要修的学分 ，以及各个学分有几门课，思路：母函数2014,12,3
#include<stdio.h>
#include<string.h>
int main(){
	int t,i,j,k,s,a,b,g[50],x[50],y[50],m,n;
	scanf("%d",&t);
	while(t--){
		memset(x,0,sizeof(x));
		memset(y,0,sizeof(y));
		memset(g,0,sizeof(g));
		scanf("%d%d",&m,&n);
		for(i=1;i<=n;i++){
			scanf("%d%d",&a,&b);
			g[a]=b;//记录不同学分的课程各有几个 
		}
		for(i=0;i<=g[1];i++)//为什么小于g[1] ，还没看懂，继续看看，哪个大神懂，求指教
			x[i]=1;
		for(i=2;i<=8;i++){
			for(j=0;j<=40;j++)
				for(k=0,s=0;s<=g[i]&&k+j<=40;k+=i,s++)//s表示这个学分的有几个 
					y[k+j]+=x[j];
			for(j=0;j<=40;j++){
				x[j]=y[j];
				y[j]=0;
			}
		}
		printf("%d\n",x[m]);
	}
	return 0;
}


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


联系
我们