蚂蚁的难题(八)
时间限制：2000 ms | 内存限制：65535 KB
难度：5
- 描述
-
蚂蚁是一个古玩爱好者，他收藏了很多瓶瓶罐罐。
有一天，他要将他的宝贝们一字排开， 摆放到一个长度为L的展台上。
已知他有n件宝贝， 每件宝贝的宽为w,由于这些瓶瓶罐罐的形状特殊，所以在摆放时需要至少X的宽度来摆放他们，（仅摆放时需要X的宽度， 摆放后宽度仍为w）现在已知了每件宝贝的宽度wi，和摆放它们所需的宽度Xi。请你帮蚂蚁计算一下，在这个展台上，他最多能摆多宽的宝贝。
- 输入
- 有多组测试数据。
对于每一组测试数据：
第一行： n L 分别代表有n件宝贝，展台长度为L;(n<1000, L<10000)
接下来有n行, 每行有两个整数 wi xi 分别代表第i件宝贝的宽度和摆放时需要的宽度。（0<wi <= xi < 10000）. - 输出
- 输出蚂蚁能够摆出的最大的宽度。
- 样例输入
-
3 10
2 3
3 4
4 7 - 样例输出
-
9
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define NN 10010
struct T
{
int x,y,c;
}num[NN];
int cmp(T m, T n)
{
if(m.c>n.c)
return ;
return ;
}
int dp[NN];
int main()
{
int i,j,k,t,m,n,M,N,nn,mm;
while(cin>>m>>n)
{
memset(dp,,sizeof(dp));
int k=;
for(i=; i<m; i++)
{
cin>>M>>N;
if(N<=n)
{num[k].x=M;num[k].y=N;num[k].c=N-M; k++;}
}
sort(num,num+k,cmp);//按照差值进行排序；
int kk=-;
for(i=; i<k ; i++)
{ for(j=n; j>=num[i].x; j--)
{
if(n-num[i].y >= j-num[i].x)//判断是否还能往箱子里放
{
dp[j]=max(dp[j],dp[j-num[i].x]+num[i].x);
kk=max(dp[j],kk);
}
}
}
cout<<kk<<endl;
}
return ;
}