SP39 PIGBANK - Piggy-Bank

题目传送门

解题思路

这题就是完全背包，只不过把max改为min就行了（再加个特判）

AC代码

#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,k,T,v[100005],w[100005],f[100005];
int main()
{
	cin>>T;
	while(T--)
	{
		scanf("%lld%lld",&n,&m);
		m=m-n;//m
		for(int i=1;i<=m;i++)f[i]=2147483647;//初值
		f[0]=0;
		scanf("%lld",&k);
		for(int i=1;i<=k;i++)//完全背包
		{
			scanf("%lld%lld",&v[i],&w[i]);
			for(int j=w[i];j<=m;j++)
			 f[j]=min(f[j],f[j-w[i]]+v[i]);//min
		}
		if(f[m]==2147483647)cout<<"This is impossible."<<endl;//特判
		else cout<<"The minimum amount of money in the piggy-bank is "<<f[m]<<"."<<endl;
	}
}

谢谢