|
|
Posted on 2010-08-03 22:49 MiYu 阅读(680) 评论(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
|