UVa 147 - Dollars

题目：有一些面值的钱币，问组成面值n，有多少种方法。

分析：dp，完全背包。整数拆分用背包。

说明：使用long long防止溢出。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

long long F[30003];
int C[11] = {10000,5000,2000,1000,500,200,100,50,20,10,5};

int main()
{
	for (int i = 0 ; i <= 30000 ; ++ i)
		F[i] = 0LL;
	F[0] = 1LL;
	for (int i = 0 ; i < 11 ; ++i)
	for (int j = C[i] ; j <= 30000 ; ++ j)
		F[j] += F[j-C[i]];
	
	int  a,b;
	while (~scanf("%d.%d",&a,&b) && a+b)
		printf("%3d.%02d%17lld\n",a,b,F[100*a+b]);
	
    return 0;
}

UVa 147 - Dollars

原文：http://blog.csdn.net/mobius_strip/article/details/41078271