无知 无求

0%

hdu1114 Piggy-Bank

发表于 分类于 ，

显而易见的多重背包。。没啥说的。。直接找最小值就好。。就是初始化时候要初始化最大值，memeset默认按char作为内容来赋值的，所以最大值的设置需要一点点技巧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=0x3f3f3f3f;
int dp[20020];
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        memset(dp,maxn,sizeof(dp));
        int before,after;
        scanf("%d%d",&before,&after);
        int upsum=after-before;
        dp[0]=0;
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;++i){
            int v,w;
            scanf("%d%d",&v,&w);
            for(int j=0;j<upsum;++j){
                if(dp[j]!=maxn){
                    dp[j+w]=min(dp[j+w],dp[j]+v);
                }
            }
        }
        if(dp[upsum]!=maxn){
            printf("The minimum amount of money in the piggy-bank is %d.\n",dp[upsum]);
        }else{
            printf("This is impossible.\n");
        }
    }
    return 0;
}