提交时间:2024-05-05 08:32:10
运行 ID: 145434
#include<bits/stdc++.h> using namespace std; const int N=205; int T,e,F,n; int main(){ cin>>T; for(int t=1;t<=T;t++){ cin>>e>>F>>n; 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-e;i++)f[i]=0x7fff; for(int i=1;i<=n;i++){ for(int j=w[i];j<=F-e;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-e]<<".\n"; } }