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