*UVA 147 Dollars

题目描述

完全背包问题

首先把所有的硬币都转换成美分

设DP[i][v]为v分钱，选了前i种钱的方法总数

其实对于第i种货币我们有选和不选两种状态

所以可以很轻松的得到状态转移方程：

dp[i][v]=dp[i-1][v]+dp[i][v-a[j]]; 但是我们可以很轻松的注意到

i这一维是可以省去的

所以总的状态方程就为：

dp[v]+=dp[v-a[j]];

#include<cstdio>
long long a[6005];
int coin[]={1,2,4,10,20,40,100,200,400,1000,2000};
int main(){
	for(int i=0;i<=6000;i++)
	a[i]=1;
	for(int i=1;i<11;i++){
		for(int j=coin[i];j<=6000;j++)
		a[j]+=a[j-coin[i]]; 
	}
	while(true){
		double d;
		scanf("%lf",&d);
		if(d==0.0)break;
		int n=int(d*20.0);
		printf("%6.2lf%17lld\n",d,a[n]);
	}
	return 0;
}