HDU 1114 Piggy-Bank(完全背包模板题)

完全背包模板题

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define inf 0x3f3f3f3f

int w[],v[],f[];

int main()

{

    int T,v1,v2,n;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&v1,&v2);

        scanf("%d",&n);

        int vn=v2-v1;

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

            f[i]=inf;

        f[]=;

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

            scanf("%d%d",&w[i],&v[i]);

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

            for(int j=v[i];j<=vn;j++)

                f[j]=min(f[j],f[j-v[i]]+w[i]);

        }

        if(f[vn]!=inf)

            printf("The minimum amount of money in the piggy-bank is %d.\n",f[vn]);

        else

            printf("This is impossible.\n");

    }

}