uva 10154 贪心+dp

题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1095

题目大意：有许多只王八，每一只王八有着两个属性，重量w和力量s，这些王八最多能叠多少层不会让出现王八被压死，注意王八承受的重量

要算上自己的重量

思路分析：首先是贪心，我们要选择力量最大的王八放在下面是最优的，证明如下

分析，如果力量大的在下面，力量小的在上面，那么力量大的还能承受的重力就是s[da]-w[xiao]-w[da]，力量小的能够承受的重力为s[xiao]，前者可能大于，等于，或小于后者；如果力量小的在下面，力量大的在上面，那么力量小的能够承受的重力就是s[xiao]-w[xiao]-w[da]，力量大的能够承受的重力为s[da],前者一定小于后者，总的承重能力受制于前者。这两种方式 第二种的总的承重能力显然不及第一种，也就是第一种更优，所以力量大的在下面一定比力量轻的在下面更好。所以我们按力量排序。

按力量排序以后然后dp[i]代表叠i层所需要的最小的重量，按照01背包写法01滚动即可

代码：

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

using namespace std;

const int maxn=;

struct node

{

    int w;

    int s;

};

node t[maxn];

int dp[maxn];

bool cmp(node a,node b)

{

    if(a.s==b.s) return a.w<b.w;

    else return a.s<b.s;

}

const int inf=0xfffff;

int main()

{

     int a,b;

     int tot=;

     while(scanf("%d%d",&a,&b)!=EOF)

     {

         if(b>=a) t[tot].w=a,t[tot++].s=b;

          // if(tot==5) break;

     }

     sort(t+,t+tot,cmp);

     for(int i=;i<tot;i++)

     {

         dp[i]=inf;

     }

     dp[]=;

     int ans=;

     for(int i=;i<tot;i++)

     {

         for(int j=tot-;j>=;j--)

         {

             if(t[i].s>dp[j-]+t[i].w)

             {

                dp[j]=min(dp[j],dp[j-]+t[i].w);

                if(dp[j]<inf)

                    ans=max(ans,j);

             }

         }

     }

     printf("%d\n",ans);

}