1 /*
2 题意：有很多乌龟，每只有它的重量和承重，包括它自己的重量，
3 例如 重 300g，承重1000g，则实际承重700.
4 问最多有多少只乌龟可以叠在一起。
5
6 定义dp[i][j]为第 i 只乌龟 叠到第 j 层的重量。
7 则当 a[i].p-a[i].w>=dp[j-1]时（也就是这只乌龟可以承受之前 j-1 层的重量 ）
8 dp[j]=min(dp[j],dp[j-1]+a[i].w);
9 看了题解才造= = 向不看题解努力
10 另又学到了一种初始化的方式。就是初始化0x3f3f3f3f
11
12 详见 http://www.java123.net/v/957592.html
13 */
14 #include<cstdio>
15 #include<cstring>
16 #include<algorithm>
17 #define INF 0x3f3f3f3f
18 using namespace std;
19 struct node
20 {
21 int w,p;
22 }a[5700];
23 bool cmp(node xx,node yy)
24 {
25 return (xx.p-xx.w)<(yy.p-yy.w);
26 }
27 int dp[5700];
28 int main()
29 {
30 int cnt=0,p,q;
31 while(scanf("%d%d",&p,&q)!=EOF)
32 {
33 cnt++; a[cnt].w=p, a[cnt].p=q;
34 }
35 sort(a+1,a+cnt+1,cmp);
36 memset(dp,0x3f,sizeof(dp));
37 dp[0]=0;
38 int ans=0;
39 for(int i=1;i<=cnt;i++)
40 {
41 for(int j=cnt;j>=1;j--)
42 {
43 if(a[i].p-a[i].w >= dp[j-1])
44 {
45 dp[j]=min(dp[j],dp[j-1]+a[i].w);
46 if(dp[j]<INF) ans=max(ans,j);
47 }
48 }
49 }
50 printf("%d
",ans);
51 return 0;
52 }
