uva147 Dollars ——完全背包

link:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=83

和完全背包一样的思想。

有两个trick：

浮点数转化成整数的时候，注意精度。
因为题目中说了都是5的倍数，所以可以都除以5.

没了。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cmath>
 6 #include <cctype>
 7 #include <algorithm>
 8 #include <queue>
 9 #include <deque>
10 #include <queue>
11 #include <list>
12 #include <map>
13 #include <set>
14 #include <vector>
15 #include <utility>
16 #include <functional>
17 #include <fstream>
18 #include <iomanip>
19 #include <sstream>
20 #include <numeric>
21 #include <cassert>
22 #include <ctime>
23 #include <iterator>
24 const int INF = 0x3f3f3f3f;
25 const int dir[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
26 using namespace std;
27 long long d[33333];
28 int a[11]={5,10,20,50,100,200,500,1000,2000,5000,10000};
29 int main(void) {
30     ios::sync_with_stdio(false);
31 #ifndef ONLINE_JUDGE
32     freopen("in.txt","r",stdin);
33 #endif
34     double tmp;
35     while(cin>>tmp) {
36         int n; 
37         //n=(int)(tmp*100);
38         n=(int)(0.5+tmp*100);
39         n/=5;
40         if(!n) break;
41         memset(d,0,sizeof(d)); 
42         d[0]=1;
43         for (int i=0;i<11;++i) {
44             for (int j=a[i]/5;j<=n;++j) {
45                 d[j]+=d[j-a[i]/5];
46             }
47         }
48         printf("%6.2f%17lld
",tmp,d[n]);
49     }
50     return 0;
51 }

o(╯□╰)o

因为精度那个东西WA了。