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 ;
}