hdu1114 Piggy-Bank ——完全背包

link:http://acm.hdu.edu.cn/showproblem.php?pid=1114

只不过求得是最小值。没什么可说的，连我都会做……o(╯□╰)o

 1 /*
 2 ID: zypz4571
 3 LANG: C++
 4 TASK: pig.cpp
 5  */
 6 
 7 #include <iostream>
 8 #include <cstdio>
 9 #include <cstdlib>
10 #include <cstring>
11 #include <cmath>
12 #include <cctype>
13 #include <algorithm>
14 #include <queue>
15 #include <deque>
16 #include <queue>
17 #include <list>
18 #include <map>
19 #include <set>
20 #include <vector>
21 #include <utility>
22 #include <functional>
23 #include <fstream>
24 #include <iomanip>
25 #include <sstream>
26 #include <numeric>
27 #include <cassert>
28 #include <ctime>
29 #include <iterator>
30 const int INF = 0x3f3f3f3f;
31 const int dir[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
32 using namespace std;
33 int f[11111],c[555],w[555], V, n;
34 void completepack(int c,int w) {
35     for(int v=c;v<=V;++v) 
36             f[v]=min(f[v],f[v-c]+w);
37 }
38 int main ( int argc, char *argv[] )
39 {
40 #ifndef ONLINE_JUDGE
41 freopen("in.txt", "r", stdin);
42 #endif
43     ios::sync_with_stdio(false);
44     int t; cin>>t;
45     while (t--) {
46         int e, F; cin>>e>>F; V=F-e; cin>>n;
47         for(int i=0;i<n;++i) cin>>c[i]>>w[i];
48         memset(f,INF,sizeof(f)); f[0]=0;
49         for (int i=0;i<n;++i) completepack(w[i],c[i]);
50         if(f[V]==INF) cout<<"This is impossible.
";
51         else cout<<"The minimum amount of money in the piggy-bank is "<<
52             f[V]<<".
";
53     }
54         return EXIT_SUCCESS;
55 }                /* ----------  end of function main  ---------- */

o(╯□╰)o