//MiYu原创, 转帖请注明 : 转载自 ______________白白の屋题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2079题目描述:
Describtion
又到了选课的时间了，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个学分的组合数。
很简单的题目, 看上去就是直接母函数了, 而且还比较标准.
代码如下:
//MiYu原创, 转帖请注明 : 转载自 ______________白白の屋
#include <iostream>
using namespace std;
int score[9];
int amt[9];
int num1[41];
int num2[41];
int main ()
{
int T;
while ( cin >> T )
{
while ( T -- )
{
int N,K;
cin >> N >> K;
for ( int i = 1; i<= K; ++ i )
{
cin >> score[i] >> amt[i];
}
for ( int i = 0; i <= N; ++ i )
{
num1[i] = num2[i] = 0;
}
num1[0] = 1;
for ( int i = 1; i <= K; ++ i )
{
for ( int j = 0; j <= N; ++ j )
{
for ( int k = 0; k <= amt[i] && k * score[i] + j <= N; ++ k )
{
num2[ k * score[i] + j ] += num1[j];
}
}
for ( int j = 0; j <= N; ++ j )
{
num1[j] = num2[j];
num2[j] = 0;
}
}
cout << num1[N] << endl;
}
}
return 0;
}
这道题的数据是比较小的, 所以可以直接暴力AC, 这样想起来, 暴力似乎更加简单直观, 所以以后做题的时候应该先分析题目数据的规模, 以免浪费比赛时间, 当然,平常练习时不建议暴力.
暴力代码: ( 非本人所写, 据说HDU上 可以0k 0ms过, 没试过 )
#include <stdio.h>
int main(void)
{
int c[9], k, n, i;
int count;
int t[9], a, b;
int total = 40;
scanf("%d", &k);
while (k-- && scanf("%d%d", &total, &n))
{
for (count = i = 0; i < 9; t[i++] = 0);
for (i = 0; i < n; i++)
{
scanf("%d%d", &a, &b);
t[a] = b;
}
for (c[8] = 0; c[8] <= t[8] && c[8] * 8 <= total; c[8]++)
for (c[7] = 0; c[7] <= t[7] && c[8] * 8 + c[7] * 7 <= total; c[7]++)
for (c[6] = 0; c[6] <= t[6] && c[8] * 8 + c[7] * 7 + c[6] * 6 <= total; c[6]++)
for (c[5] = 0; c[5] <= t[5] && c[8] * 8 + c[7] * 7 + c[6] * 6 + c[5] * 5 <= total; c[5]++)
for (c[4] = 0; c[4] <= t[4] && c[8] * 8 + c[7] * 7 + c[6] * 6 + c[5] * 5 + c[4] * 4 <= total; c[4]++)
for (c[3] = 0; c[3] <= t[3] && c[8] * 8 + c[7] * 7 + c[6] * 6 + c[5] * 5 + c[4] * 4 + c[3] * 3 <= total; c[3]++)
for (c[2] = 0; c[2] <= t[2] && c[8] * 8 + c[7] * 7 + c[6] * 6 + c[5] * 5 + c[4] * 4 + c[3] * 3 + c[2] * 2 <= total; c[2]++)
{
c[1] = total - (c[8] * 8 + c[7] * 7 + c[6] * 6 + c[5] * 5 + c[4] * 4 + c[3] * 3 + c[2] * 2);
if (c[1] >= 0 && c[1] <= t[1]) count++;
}
printf("%d\n", count);
}
return 0;
}