题目链接：http://acm.tju.edu.cn/toj/showp3991.html 题意：给我们每一天学习的值和吃的值，然后给我们必须要到的学习的值，然后问我们到必须要学习到的值的时候最大满足的吃的值。 一开始
题目链接：http://acm.tju.edu.cn/toj/showp3991.html
题意：给我们每一天学习的值和吃的值，然后给我们必须要到的学习的值，然后问我们到必须要学习到的值的时候最大满足的吃的值。
一开始一看，这个问题有点像是背包，但是又一个问题那就是我们背包问题的体积和价值是连在一起的，也就是说我们是放入一定体积下同时获得的价值，但现在我们是要么学习，要么吃，看起来就不能用到背包。
但是实际上我们可以转换这个问题，我们把学习的值和吃的值绑定在一起，那么这个时候我们学习的时候同时就能吃，但是实际上我们是不能这样的，所以现在我们获得的吃的值，就相当于总的吃的值，减去我们绑在一起的学习时又同时吃的值，那么为了让吃的值越大，就相当于让我们在满足学习的值时同时得到的吃的值越小，所以我们就可以用背包DP求得最大值。
#include <iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
int main()
{
int t;
int p[150],v[150];
int dp[150];
cin>>t;
while(t--)
{
int n,m;
int ans=0;
cin>>n>>m;
for(int i=0; i<=m; i++)
dp[i]=INF;
for(int i=0; i<n; i++)
{
cin>>p[i]>>v[i];
ans+=v[i];
}
for(int i=0; i<n; i++)
for(int j=m; j>=0; j--)
if(j <= p[i])
dp[j]=min(dp[j],v[i]);
else
dp[j]=min(dp[j],dp[j-p[i]]+v[i]);
if(dp[m]<INF)
cout<<(ans-dp[m])<<endl;
else
cout<<"JUMP DOWN!"<<endl;
}
return 0;
}