UVA-147 Dollars---完全背包+打表

题目链接：

题目大意：

给定11种面值分别为$100, $50, $20, $10, and $5 notes and $2, $1, 50c, 20c, 10c and 5c coins的钱，现在给定一个钱数，求出可以组成的种类数，类似于uva 674，不过此题的精度太强了，纠结。。。

int n=(int)(nn*100+0.5);，注意用long long ,种类数可能非常大

用dp[i][j]表示用前i种硬币，组成j分的种类数，

状态转移方程：dp[i][j]+=DP(i-1,j-k*d[i]);

和UVA-674类似

 #include<iostream>

 #include<vector>

 #include<queue>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<set>

 #include<map>

 #include<cmath>

 #include<sstream>

 using namespace std;

 typedef pair<int, int> Pair;

 typedef long long ll;

 const int INF = 0x3f3f3f3f;

 int T, n, m,d;

 const int maxn = 3e4 + ;

 int a[] = {,,,,,,,,,,};

 ll dp[maxn];

 //dp[i][j]表示前i种货币凑成价值j的种数

 //dp[i][j] = dp[i - 1][j] + dp[i - 1][j - w[i]]

 int main()

 {

     dp[] = ;

     for(int i = ; i < ; i++)

         for(int j = a[i]; j < maxn; j++)

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

     double c;

     while(cin >> c)

     {

         if(c == )break;

         n = c *  + 0.5;//精度处理

         printf("%6.2f%17lld\n", c, dp[n]);

     }

     return ;

 }