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

作者：cgl1079743846

补充：软件开发 , C++ ,