首页 > ACM题库 > HDU-杭电 > hdu 2566 统计硬币-[解题报告]C++
2014
02-10

hdu 2566 统计硬币-[解题报告]C++

统计硬币

问题描述 :

假设一堆由1分、2分、5分组成的n个硬币总面值为m分,求一共有多少种可能的组合方式(某种面值的硬币可以数量可以为0)。

输入:

输入数据第一行有一个正整数T,表示有T组测试数据;
接下来的T行,每行有两个数n,m,n和m的含义同上。

输出:

输入数据第一行有一个正整数T,表示有T组测试数据;
接下来的T行,每行有两个数n,m,n和m的含义同上。

样例输入:

2
3 5
4 8

样例输出:

1
2

2011-12-31 19:13:38

地址:http://acm.hdu.edu.cn/showproblem.php?pid=2566

题意:中文。。。

mark:题目没给数据范围,实在蛋疼,水了一下。

考虑到如果有n个硬币,全都是1或2,能组成[n,2n]区间内任何一个数。

所以枚举面额为5的硬币个数,然后计算剩下的面额是否在剩下的1、2硬币组成的面额区间内。15ms。

那个dp[]数组没用,一开始看错题了。

代码:

# include <stdio.h>

int dp[] = {1, 1, 2, 3, 5, 9} ;

int main ()
{
    int T, i, n, m, nn, mm, ans ;
    scanf ("%d", &T) ;
    while (T--)
    {
         scanf ("%d%d", &n, &m) ;
        ans = 0 ;
        for (i = 0 ; i <= n && 5*i <= m ; i++)
        {
            mm = m - 5*i ;
            nn = n - i ;
            if (mm >= nn && mm <= 2*nn) ans++ ;
        }
        printf ("%d\n", ans) ;
    }
    return 0 ;
}

解题转自:http://www.cnblogs.com/lzsz1212/archive/2012/01/07/2315439.html


  1. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环