UVA 10154:Weights and Measures

 Weights and Measures 

题目链接：

题意：

给出一些乌龟，每只乌龟有两个值，重量a和力量b，每只乌龟可以承受b-a的重量，求把这些乌龟竖直叠在一起最多能叠多少只乌龟。

题解：

设乌龟X和乌龟Y都是答案所求的乌龟数中的两只，且Xb>Yb，可以发现min(Xb-Xa-Ya,Yb-Ya)恒大于min(Yb-Ya-Xa,Xb-Xa)，因此力量大的乌龟一定在下边，可以将乌龟按重量排序。设dp[i][j]为前 i 只乌龟叠到第 j 层所剩可利用资源的最大值即可，由于数据比较大可采用滚动数组。

代码

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

const int maxn=60005;

struct node

{

　　int a,b;

}A[maxn];

int cmp(node u,node v)

{

　　return u.b>v.b;

}

int dp[maxn][2];

int main()

{

　　int tot=1;

　　while(~scanf("%d%d",&A[tot].a,&A[tot].b))

　　{

　　　　tot++;

　　}

　　tot--;

　　sort(A+1,A+tot+1,cmp);

　　memset(dp,-1,sizeof(dp));

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

　　dp[i][0]=max(A[i].b-A[i].a,dp[i-1][0]);

　　int res=1;

　　for(int j=1;j<=tot;++j)

　　{

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

　　　　{

　　　　　　dp[i][1]=dp[i-1][1];

　　　　　　dp[i][1]=max(dp[i][1],min(dp[i-1][0]-A[i].a,A[i].b-A[i].a));

　　　　　　if(dp[i][1]>=0)res=j+1;

　　　　}

　　　　for(int k=1;k<=tot;++k)

　　　　{

　　　　　　dp[k][0]=dp[k][1],dp[k][1]=-1;

　　　　}

　　}

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

　　return 0;

}

转载于:https://www.cnblogs.com/kiuhghcsc/p/5801168.html