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