https://vjudge.net/contest/353157#problem/A

一开始用的记忆化搜索= =

样例能过不知道为啥提交WA

= 。=    = 。=

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <map>
 5 #define INF 0x3fffffff
 6 using namespace std;
 7 int book[10000+1];
 8 int f(int now_size,map<int,int> & dict){
 9     if(book[now_size] == -1){
10         int ans = INF;
11         for(map<int,int> :: iterator it = dict.begin(); it != dict.end(); it++){
12             if(it->second <= now_size){
13                 ans = min(ans,f(now_size - it->second,dict) + it->first);
14             }
15         }
16         book[now_size] = ans;
17     }
18     return book[now_size];
19 }
20 int main(){
21     int t,empty,full;
22     cin >> t;
23     while(t--){
24         memset(book,-1,sizeof(book));
25         book[0] = 0;
26         cin >> empty >> full;
27         if(full < empty)cout<<"This is impossible."<<endl;
28         else if(full == empty)cout<<"The minimum amount of money in the piggy-bank is 0."<<endl;
29         else{
30             int coins_weight = full - empty;
31             int type;
32             cin >> type;
33             map<int,int> dict;
34             int v,w;
35             for(int i = 1; i <= type; i++){
36                 cin >> v >> w;
37                 if(dict.count(v)){
38                     if(w < dict[v])
39                         dict[v] = w;
40                 }else dict[v] = w;
41             }
42             int p = f(coins_weight,dict);
43             if(p ！= INF){
44                 cout << "The minimum amount of money in the piggy-bank is " << p << "." << endl;
45             }else{
46                 cout<<"This is impossible."<<endl;
47             }
48         }
49     }
50     return 0;
51 }

正解是完全背包来做。

 1 #include <iostream>
 2 #define INF 0x3fffffff
 3 using namespace std;
 4 struct node{
 5     int v;
 6     int w;
 7 };
 8 int main(){
 9     int t;
10     cin >> t;
11     while(t--){
12         int dp[10000 + 1];
13         node arr[501];
14         int empty,full;
15         cin >> empty >> full;
16         int n,flag = 1;
17         cin >> n;
18         for(int i = 1; i <= n; i++)
19             cin >> arr[i].v >> arr[i].w;
20         
21         if(empty == full)cout<<"The minimum amount of money in the piggy-bank is 0."<<endl;
22         else if(empty > full)cout<<"This is impossible."<<endl;
23         else flag = 0;
24         if(flag)continue;
25         int size = full - empty;
26         fill(dp,dp+size+1,INF);
27         dp[0] = 0;
28         for(int i = 1; i <= n; i++)
29             for(int j = arr[i].w; j <= size; j++){
30                 dp[j] = min(dp[j],dp[j-arr[i].w] + arr[i].v);
31             }
32         if(dp[size] == INF)cout<<"This is impossible."<<endl;
33         else cout<<"The minimum amount of money in the piggy-bank is "<<dp[size]<<"."<<endl;
34     }
35     return 0;
36 }