//MiYu原創(chuàng), 轉(zhuǎn)帖請(qǐng)注明 : 轉(zhuǎn)載自 ______________白白の屋題目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2079題目描述:
Describtion
又到了選課的時(shí)間了，xhd看著選課表發(fā)呆，為了想讓下一學(xué)期好過點(diǎn)，他想知道學(xué)n個(gè)學(xué)分共有多少組合。你來幫幫他吧。（xhd認(rèn)為一樣學(xué)分的課沒區(qū)別）
Input
輸入數(shù)據(jù)的第一行是一個(gè)數(shù)據(jù)T，表示有T組數(shù)據(jù)。
每組數(shù)據(jù)的第一行是兩個(gè)整數(shù)n(1 <= n <= 40)，k(1 <= k <= 8)。
接著有k行，每行有兩個(gè)整數(shù)a(1 <= a <= 8),b(1 <= b <= 10)，表示學(xué)分為a的課有b門。
Output
對(duì)于每組輸入數(shù)據(jù)，輸出一個(gè)整數(shù)，表示學(xué)n個(gè)學(xué)分的組合數(shù)。
很簡單的題目, 看上去就是直接母函數(shù)了, 而且還比較標(biāo)準(zhǔn).
代碼如下:
//MiYu原創(chuàng), 轉(zhuǎn)帖請(qǐng)注明 : 轉(zhuǎn)載自 ______________白白の屋
#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;
}
這道題的數(shù)據(jù)是比較小的, 所以可以直接暴力AC, 這樣想起來, 暴力似乎更加簡單直觀, 所以以后做題的時(shí)候應(yīng)該先分析題目數(shù)據(jù)的規(guī)模, 以免浪費(fèi)比賽時(shí)間, 當(dāng)然,平常練習(xí)時(shí)不建議暴力.
暴力代碼: ( 非本人所寫, 據(jù)說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;
}