HDU——2566 统计硬币 （简单枚举 || 母函数）

Problem Description

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

Input

输入数据第一行有一个正整数T，表示有T组测试数据；

接下来的T行，每行有两个数n,m，n和m的含义同上。

Output

对于每组测试数据，请输出可能的组合方式数；

每组输出占一行。

Sample Input

2

3 5

4 8

Sample Output

1

2

解题思路：

方法一 ： 拿到这个题目 ， 三层循环就可以解决，但是时间复杂度太高 ，为O(n^3).此基础上，因为总量是确定的，确定了前两个的个数之后 ， 第三个也能够确定 ， 所以可以减少一层循环，时间复杂度也可以相对降低一点 ， 为 O(n^2).

代码：

//方法一 直接枚举 ， 时间复杂度为 O（n^)
/*
#include <cstdio>
#include <cstring>
using namespace std;

int value[] = { ,  ,  , };
int main(){
    int t , n , m , i , j , k ,ans;
    scanf("%d", &t);
    while( t --){
        ans = ;
        scanf("%d %d",&n , &m);
        for(i =  ; i <= n ; i ++){
            for(j =  ; j + i <= n ; j ++){
                    if( * i +  * j +  * (n - i - j) == m)
                        ans ++;
            }
        }
        printf("%d\n" , ans);
    }
    return ;
}
           

方法二：因为当只要考虑面值为 1 和 2 的硬币的组合情况时 ， 当总面值确定时 ， 每一个总面值有也仅有一种组合情况 。 利用一点 ， 我们可以先确定面值为 5 的纸币的数量，然后在考虑面值1和2 ， 这样时间复杂度就可以很大的降低 ，为 O(m).

代码：

//方法二 加了那么一点点技巧 ， 主要时间复杂度可以降低很多
//考虑如果只有面值为1、2的硬币n枚。那么能够唯一组成区间[n,2n]范围里的任意面值。

#include <cstdio>
using namespace std;

int main(){
    int t , n , m , i,ans;
    scanf("%d", &t);
    while( t --){
        ans = ;
        scanf("%d %d",&n , &m);
        for(i =  ; i <= m/ && i <= n; i ++){  //首先确定面值为5 的硬币可能出现的张数。
            int temp = m - i*;  //剩下的面值
            int tempcount = n - i;  //剩下的张数

            if(tempcount *  <= temp && tempcount *  >= temp)
                ans ++;
        }
        printf("%d\n" , ans);
    }
    return ;
}