Posted on 2010-08-03 22:49
MiYu 閱讀(725)
評論(0) 編輯 收藏 引用 所屬分類:
ACM ( 母函數 ) 、
ACM ( 枚舉 ) 、
ACM ( 水題 )
//MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋
題目地址 :
http://acm.hdu.edu.cn/showproblem.php?pid=2069
目前每日平均WA次數 20次以上...................................
晚上做一道水題 HDOJ 2069 ACM IN HDU, 又跟上次的 TLE 的 -1 一樣, 題目的最后一段是文件結束的說明,
都沒怎么自習去看, 結果直接就WA了.............最后在 元帥的提醒下, 原來這題真的很水,就跟剛學編程時做的
100錢買小雞,公雞,母雞 100只一樣, 是可以直接暴力的, 因為數據不大. 當然,也可以用 母函數來做, 不過需要
增開輔助空間 :
c1[i][j] 表示i分錢由j個硬幣組成的方案數 , 然后在循環中增加一個循環 :用于保存在當前硬幣數量k上增加
1 - n 個硬幣時 ( k + n < =100 ) 方案數
暴力代碼:
//MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋
1 #include <iostream>
2 int main()
3 {
4 int n, d[251] = { 0 };
5 int c1, c5, c10, c25, c50;
6 for ( n = 0; n != 251; n ++ )
7 {
8 for ( c50 = 0; c50 * 50 <= n; c50 ++ )
9 {
10 for ( c25 = 0; c50 * 50 + c25 * 25 <= n; c25++ )
11 {
12 for ( c10 = 0; c50 * 50 + c25 * 25 + c10 * 10 <= n; c10++ )
13 {
14 for ( c5 = 0; c50 * 50 + c25 * 25 + c10 * 10 + c5 * 5 <= n; c5++ )
15 {
16 c1 = n - ( c50 * 50 + c25 * 25 + c10 * 10 + c5 * 5 );
17 if ( c1 + c5 + c10 + c25 + c50 <= 100 )
18 {
19 d[n]++;
20 }
21 }
22 }
23 }
24 }
25 }
26 while ( ~scanf("%d", &n) )
27 {
28 printf ( "%d\n", d[n] );
29 }
30 return 0;
31 }
32
母函數代碼 :
1 #include <iostream>
2 using namespace std;
3 int c1[251][101];
4 int c2[251][101];
5 int mon[6] = { 0, 1, 5, 10, 25, 50 };
6 int sum[251];
7 int main ()
8 {
9 c1[0][0] = 1;
10 for ( int i = 1; i <= 5; ++ i )
11 {
12 for ( int j = 0; j <= 250; ++ j )
13 {
14 for ( int k = 0; k * mon[i] + j <= 250; ++ k )
15 {
16 for ( int p = 0; p + k <= 100; ++ p )
17 {
18 c2[ j + k * mon[i] ][p + k] += c1[j][p];
19 }
20 }
21 }
22 for ( int j = 0; j != 251; ++ j )
23 {
24 for ( int k = 0; k != 101; ++ k )
25 {
26 c1[j][k] = c2[j][k];
27 c2[j][k] = 0;
28 }
29 }
30 }
31 for ( int j = 0; j != 251; ++ j )
32 {
33 for ( int i = 0; i != 101; ++ i )
34 {
35 sum[j] += c1[j][i] ;
36 }
37 }
38 int N;
39 while ( cin >> N )
40 {
41
42 cout << sum[N] << endl;
43 }
44 return 0;
45 }
46