提交时间:2024-05-05 08:35:13
运行 ID: 145439
#include<bits/stdc++.h> using namespace std; const int N=10009; int T,e,F,n; int main(){ cin>>T; for(int t=1;t<=T;t++){ cin>>e>>F>>n; F-=e; int p[N],f[N],w[N]; f[0]=0; for(int i=1;i<=n;i++)cin>>p[i]>>w[i]; for(int i=1;i<=F;i++)f[i]=0x7fff; for(int i=1;i<=n;i++){ for(int j=w[i];j<=F;j++){ f[j]=min(f[j],f[j-w[i]]+p[i]); } } //for(int i=0;i<=F-e;i++)cout<<f[i]<<' '; if(f[n]==0x7fff)cout<<"This is impossible.\n"; else cout<<"The minimum amount of money in the piggy-bank is "<<f[F]<<".\n"; } }