HDU 2079 选课时间(题目已修改,注意读题) [母函数]

雨点打透心脏的1/2处 2022-05-30 12:44 119阅读 0赞

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

**Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 5661    Accepted Submission(s): 4296**

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

Author

xhd

Source

[ACM程序设计期末考试\_热身赛(感谢 xhd & 8600)][ACM_ xhd _ 8600]

Recommend

lcy   |   We have carefully selected several similar problems for you:   [2110][]  [2189][]  [2566][]  [2077][]  [2066][]

#include <stdio.h>
    #include <string.h>	
    #include <algorithm>
    using namespace std;
    int a[100],b[100];
    int c1[1005],c2[1005];
    int main(int argc, char *argv[])
    {
    	int t;
    	int n,k;
    	int i,j,kk;
    	scanf("%d",&t);
    	while(t--)
    	{
    		int sum=0;
    		scanf("%d %d",&n,&k);
    		memset(c1,0,sizeof(c1));
    		memset(c2,0,sizeof(c2));
    		for(i=1;i<=k;i++)
    			scanf("%d %d",&a[i],&b[i]);
    		for(i=0;i<=a[1]*b[1];i+=a[1])
    			c1[i]=1;
    		for(i=2;i<=k;i++)
    		{
    			for(j=0;j<=n;j++)
    			{
    				for(kk=0;kk+j<=n&&kk<=a[i]*b[i];kk+=a[i])
    					c2[j+kk]+=c1[j];
    			}
    			for(j=0;j<=n;j++)
    				c1[j]=c2[j],c2[j]=0;			
    		}		
    		printf("%d\n",c1[n]);
    	}	
    	return 0;
    }

[ACM_ xhd _ 8600]: http://acm.hdu.edu.cn/search.php?field=problem&key=ACM%B3%CC%D0%F2%C9%E8%BC%C6%C6%DA%C4%A9%BF%BC%CA%D4_%C8%C8%C9%ED%C8%FC%28%B8%D0%D0%BB+xhd+%26amp%3B+8600%29&source=1&searchmode=source
[2110]: http://acm.hdu.edu.cn/showproblem.php?pid=2110
[2189]: http://acm.hdu.edu.cn/showproblem.php?pid=2189
[2566]: http://acm.hdu.edu.cn/showproblem.php?pid=2566
[2077]: http://acm.hdu.edu.cn/showproblem.php?pid=2077
[2066]: http://acm.hdu.edu.cn/showproblem.php?pid=2066