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

点击打开链接uva 357

点击打开链接uva 147

题目意思： 和uva 674一样，都是求总方案数

解题思路： 动态规划

357

解题思路：动态规划，uva674的同类型题，但是这一题的数据n最大到30000
那么如果一直累加中间过程和是会超过int这个地方WA了N次，所以我们必须用
unsigned long long ，其它还要注意方案数为1的时候输出比较不同

代码：

#include <algorithm>#include <iostream>#include <cstring>#include <string>#include <vector>#include <cstdio>#include <stack>#include <queue>#include <cmath>using namespace std;#define MAXN 30010unsigned 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;}