//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;
}