POJ-1834 Piggy-Bank

POJ-1834 Piggy-Bank

AC code:

//By SCJ

#include<iostream>

using namespace std;

#define maxn 10000

#define INF 2100000000

int dp[maxn+1];

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   int T;cin>>T;

   while(T--)

   {

       int E,F,W;cin>>E>>F;

       W=F-E;

       for(int i=0;i<=W;++i) dp[i]=INF;

       dp[0]=0;

       int n,p,w;

       cin>>n;

       for(int K=0;K<n;++K)

       {

           cin>>p>>w;

           for(int i=w;i<=W;++i) dp[i]=min(dp[i-w]+p,dp[i]);

       }

       if(dp[W]!=INF) cout<<"The minimum amount of money in the piggy-bank is "<<dp[W]<<".\n";

       else cout<<"This is impossible.\n";

   }

}