UVA_10154

 

    首先，我们不妨证明一下这个命题，如果一个力量小的乌龟可以驮着一个力量大的乌龟，那么这个力量大的乌龟也必然可以驮起这个力量小的乌龟，而且还能够使两个乌龟上方增加承重能力。

 

    我们不妨设力量小的乌龟的重量和力量分别为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个的时候的最轻的重量，那么显然一开始f[0]应该为0，而其余的都应为INF。

 

    这样对于当前的乌龟i，如果f[j]+w[i]<s[i]且f[j]+w[i]<f[j+1]，那么我们就可以更新f[j+1]了，同时如果j+1比max要大的话，我们也需要同时更新max了。

#include
     
       #include
      
        #include
       
         #define MAXD 5700 #define INF 1000000000 int N, f[MAXD], w[MAXD], s[MAXD], r[MAXD]; int cmp(const void *_p, const void *_q) {
   int *p = (int *)_p; int *q = (int *)_q; return s[*p] - s[*q]; } void init() {
       N = 0; while(scanf("%d%d", &w[N], &s[N]) == 2)     {
   if(s[N] >= w[N])             N ++;     } } void solve() {
   int i, j, max; for(i = 0; i < N; i ++)         r[i] = i;     qsort(r, N, sizeof(r[0]), cmp); for(i = 1; i <= N; i ++)         f[i] = INF;     f[0] = 0;     max = 0; for(i = 0; i < N; i ++) for(j = max; j >= 0; j --)         {
   if(f[j] + w[r[i]] <= s[r[i]] && f[j] + w[r[i]] < f[j + 1])             {
                   f[j + 1] = f[j] + w[r[i]]; if(j + 1 > max)                     max = j + 1;             }         }     printf("%d\n", max); } int main() {
       init();     solve(); return 0; }