UVA10154 Weights and Measures

https://vjudge.net/problem/UVA-10154

↑Vjudge大法好

堆一个乌龟塔。每只乌龟有重量w和承重能力s（也要承受自己的重量，所以实际可托起s-w），问最多能堆几只乌龟

很明显是DP

从低往高堆不太好判断，因为不知道下面的乌龟还能不能承受得了。

切换到上帝视角，对于一个乌龟塔，我们可以直接把它托起来，然后在塔下面塞一只能承重的乌龟。

问题解决了。

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 const int mxn=;

 struct node{

     int w,s;

 }a[mxn];

 int cmp(const node a,const node b){

     return (a.s<b.s || (a.s==b.s && a.w<b.w));

 }

 int n;

 int f[mxn],ans;

 void solve(){

     int i,j;

     memset(f,0x3f,sizeof f);

     f[]=;ans=;

     for(i=;i<=n;i++){

         for(j=n;j;j--){

             if(f[j-]+a[i].w<=a[i].s){

                 f[j]=min(f[j],f[j-]+a[i].w);

             }

             if(f[j]<0x3f3f3f3f)ans=max(ans,j);

         }

     }

 }

 int main(){

     int i,j;

     n=;

     while(scanf("%d%d",&i,&j)!=EOF){

         if(i>j)continue;

         a[++n].w=i;a[n].s=j;

     }

     sort(a+,a+n+,cmp);

     solve();

     cout<<ans<<endl;

     return ;

 }