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

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

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

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

1 2

2 1

40 8

1 1

2 2

3 2

4 2

5 8

6 9

7 6

8 8

Sample Output

445

Author

xhd

Source

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

Recommend

lcy | We have carefully selected several similar problems for you: 2082 1398 1085 1171 2110

多重背包，不过和01背包差不多，只需要加一层循环就好，貌似还可以用母函数做，可是不会啊，以后会了再来加上，嘿嘿~

题意：中文题，很好理解。

附上代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int T,n,k,a[10],b[10],t,s,m;
 9     int dp[105],i,j,w;
10     scanf("%d",&T);
11     while(T--)
12     {
13         scanf("%d %d",&n,&k);
14         for(i=1; i<=k; i++)
15             scanf("%d %d",&a[i],&b[i]);
16         memset(dp,0,sizeof(dp));
17         dp[0]=1;
18         for(i=1; i<=k; i++)
19             for(j=n; j>=a[i]; j--)
20                 for(w=1; w<=b[i]; w++)
21                 {
22                     if(j-a[i]*w>=0)   //关键判断，以免超边界
23                         dp[j]+=dp[j-a[i]*w];
24                     else
25                         break;
26                 }
27         printf("%d
",dp[n]);
28     }
29     return 0;
30 }