uva 357 - Let Me Count The Ways 和 uva 147 - Dollars

題目意思： 和uva  674一樣，都是求總方案數
解題思路： 動態規劃

357
解題思路：動態規劃，uva674的同類型題，但是這一題的數據n最大到30000
那麼如果一直累加中間過程和是會超過int這個地方WA了N次，所以我們必須用
unsigned long long ，其它還要注意方案數為1的時候輸出比較不同

代碼：
[cpp] 
#include <algorithm> 
#include <iostream> 
#include <cstring> 
#include <string> 
#include <vector> 
#include <cstdio> 
#include <stack> 
#include <queue> 
#include <cmath> 
using namespace std; 
#define MAXN 30010 
 
int type[5] = {1,5,10,25,50}; 
unsigned long long  dp[MAXN]; 
int n; 
 
//打表處理好所有的數據 
void solve(){ 
    memset(dp , 0 , sizeof(dp)) ; dp[0] = 1; 
    for(int i = 0 ; i < 5 ; i++){ 
        for(int j = 1 ; j < MAXN ; j++){ 
          if(j-type[i] >= 0) dp[j] += dp[j-type[i]]; 
       } 
    } 
} 
 
int main(){ 
    //freopen("input.txt" , "r" , stdin); 
    solve(); 
    while(scanf("%d" , &n) != EOF) { 
        if(dp[n] > 1) printf("There are %llu ways to produce %d cents change.\n" , dp[n] , n); 
        else printf("There is only 1 way to produce %d cents change.\n" , n); 
    } 
    return 0; 
} 

147
1：由於這題的數據最大為30000，那麼如果累加的話中間值會超過int ,需要用unsigned long long才不會錯(long long 還是WA)
2：由於double類型換成整型（int s = double * 100這個是不准確的）的時候存在精度缺失，所以我們輸入的時候要用兩個整數，而不是double，最後輸出時候注意一下格式

代碼：
[cpp]
#include <algorithm> 
#include <iostream> 
#include <cstring> 
#include <string> 
#include <vector> 
#include <cstdio> 
#include <stack> 
#include <queue> 
#include <cmath> 
using namespace std; 
#define MAXN 30010 
 
unsigned long long dp[MAXN]; 
int  currency[11] = {5,10,20,50,100,200,500,1000,2000,5000,10000}; 
 
void solve(){ 
    int i , j; 
    memset(dp , 0 , sizeof(dp)) ; dp[0] = 1;  
     
    for(i = 0 ; i < 11 ; i++){ 
        for(j = 1 ; j <= MAXN ; j++){ 
            if(j-currency[i]>=0) dp[j] += dp[j-currency[i]]; 
        } 
    } 
} 
 
int main(){ 
    //freopen("input.txt" , "r" , stdin); 
    solve(); 
    int n , m , s; 
    while(scanf("%d.%d" , &n , &m)){//輸入格式 
        s = n*100+m; 
        if(s == 0) break; 
        printf("%3d.%.2d%17llu\n" , n , m , dp[s]);//輸出注意格式，前面占6個寬，後面17個寬 
    } 
    return 0; 
}