做题感悟：这题开始用力量减去自身体重去做但是一直wa，最后发现这样不对，看了某大牛的博客才恍然大悟，真想再提交 n 次AC代码以抚慰我受伤的心灵
。
解题思路：转自~~>
首先，我们不妨证明一下这个命题，如果一个力量小的乌龟可以驮着一个力量大的乌龟，那么这个力量大的乌龟也必然可以驮起这个力量小的乌龟，而且还能够使两个乌龟上方增加承重能力。
我们不妨设力量小的乌龟的重量和力量分别为w1、s1，而力量大的乌龟为w2、s2，由于乌龟1可以驮起乌龟2，那么有s1>=w1+w2，如果我们假设乌龟2驮不起乌龟1，那么就应该有s2<w1+w2，然而我们知道乌龟2的力量更大，所以应该有s2>s1>=w1+w2，这样就产生矛盾了，原命题得证。接着，如果乌龟1在乌龟2的下面，两龟上方的承重能力至多为s1-(w1+w2)。然而如果换成乌龟2在乌龟1的下面的话，对于乌龟1来讲是无所谓的，因为之前驮得动，现在少了乌龟2肯定也驮得动，因此仅从乌龟1的承重限制来讲，两龟上方的承重能力增加了。当然仅凭乌龟1的承重限制的角度来看是不全面的，我们还要考虑乌龟2，对于乌龟2来讲，两龟承重能力是s2-(w1+w2)，而前面也说到了，乌龟1在下的时候承重能力至多为s1-(w1+w2)，而s2-(w1+w2)>s1-(w1+w2)，因此从乌龟2的角度来讲，尽管上面多了个乌龟1，但就乌龟1和乌龟2作为整体而言，他们上方的承重能力也一定增加了。因此，无论两龟整体的承重能力取决于哪只龟，调换之后最终的整体承重能力一定增加了。
于是这样我们就可以先把乌龟按力量排序了，剩下的问题就是怎么求这个最长非降子序列了。
我们用max记录最多能累的乌龟的个数，显然一开始max应该是0，再设f[j]表示乌龟一共累j个的时候的最轻的重量，那么显然一开始 dp [ 0 ] 应该为0，而其余的都应为INF。这样对于当前的乌龟i，如果dp [ j ] + w[ i ] < s [ i ] 且 dp [ j ] + w [ i ] < dp [ j + 1 ] ，那么我们就可以更新 dp [ j + 1 ]了，同时如果 j +1 比 max 要大的话，我们也需要同时更新max了。
代码：
#include<stdio.h>
#include<iomanip>
#include<vector>
#include<queue>
#include<fstream>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define INT long long int
using namespace std ;
const int INF = 99999999 ;
const int MY = 15 ;
const int MX = 100000 + 10 ;
int n ;
int dp[MX] ;
struct node
{
int x,y ;
}T[MX] ;
bool cmp(node a,node b)
{
return a.y < b.y ;
}
void DP()
{
for(int i=0 ;i<n ;i++)
dp[i]=INF ;
dp[0]=0 ;
int ans=0 ;
for(int i=0 ;i<n ;i++)
{
for(int j=ans ;j>=0 ;j--)
if(T[i].y>=T[i].x+dp[j]&&dp[j+1]>T[i].x+dp[j])
{
dp[j+1]=T[i].x+dp[j] ;
ans =max(ans,j+1) ;// 不能加 break ;
}
}
cout<<ans<<endl ;
}
int main()
{
n=0 ;
while(~scanf("%d%d",&T[n].x,&T[n].y))
{
if(T[n].x<=T[n].y)
n++ ;
}
sort(T,T+n,cmp) ;
DP() ;
return 0 ;
}