首页 > 代码库 > UVA10154 Weights and Measures
UVA10154 Weights and Measures
https://vjudge.net/problem/UVA-10154
↑Vjudge大法好
堆一个乌龟塔。每只乌龟有重量w和承重能力s（也要承受自己的重量，所以实际可托起s-w），问最多能堆几只乌龟
很明显是DP
从低往高堆不太好判断，因为不知道下面的乌龟还能不能承受得了。
切换到上帝视角，对于一个乌龟塔，我们可以直接把它托起来，然后在塔下面塞一只能承重的乌龟。
问题解决了。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 const int mxn=10010; 8 struct node{ 9 int w,s;10 }a[mxn];11 int cmp(const node a,const node b){12 return (a.s<b.s || (a.s==b.s && a.w<b.w));13 }14 int n;15 int f[mxn],ans;16 void solve(){17 int i,j;18 memset(f,0x3f,sizeof f);19 f[0]=0;ans=0;20 for(i=1;i<=n;i++){21 for(j=n;j;j--){22 if(f[j-1]+a[i].w<=a[i].s){23 f[j]=min(f[j],f[j-1]+a[i].w);24 }25 if(f[j]<0x3f3f3f3f)ans=max(ans,j);26 }27 }28 }29 int main(){30 int i,j;31 n=0;32 while(scanf("%d%d",&i,&j)!=EOF){33 if(i>j)continue;34 a[++n].w=i;a[n].s=j;35 }36 sort(a+1,a+n+1,cmp);37 solve();38 cout<<ans<<endl;39 return 0;40 }
UVA10154 Weights and Measures
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。