蚂蚁的难题(八)
时间限制：
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
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 }
转载于:https://www.cnblogs.com/lovychen/p/3653976.html
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
