ntoj 808 蚂蚁的难题(八)

蚂蚁的难题(八)

时间限制：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）.

输出

输出蚂蚁能够摆出的最大的宽度。

样例输入

样例输出

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 #define NN 10010
 7 struct T
 8 {
 9     int x,y,c;
10 }num[NN];
11 int cmp(T m, T n)
12 {
13     if(m.c>n.c)
14         return 1;
15     return 0;
16 }
17 int dp[NN];
18 int main()
19 {
20     int i,j,k,t,m,n,M,N,nn,mm;
21     while(cin>>m>>n)
22     {
23         memset(dp,0,sizeof(dp));
24         int k=0;
25         for(i=0; i<m; i++)
26         {
27             cin>>M>>N;
28             if(N<=n)
29             {num[k].x=M;num[k].y=N;num[k].c=N-M; k++;}
30         }
31         sort(num,num+k,cmp);//按照差值进行排序；
32         int kk=-1;
33         for(i=0; i<k ; i++)
34         {
35 
36             for(j=n; j>=num[i].x; j--)
37             {
38                 if(n-num[i].y >= j-num[i].x)//判断是否还能往箱子里放
39                 {
40                     dp[j]=max(dp[j],dp[j-num[i].x]+num[i].x);
41                     kk=max(dp[j],kk);
42                 }
43             }
44         }
45             cout<<kk<<endl;
46     }
47     return 0;
48 }