UVA - 10154 Weights and Measures

本文主要是介绍UVA - 10154 Weights and Measures，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：有几只乌龟，每只乌龟有一定的重量与力量。每只乌龟可以背小于它力量的重量（包括它自身的重量）。问最多一共可以有多少只乌龟叠在一起。显然力量越大的在下面的话，上面就越能承受越大的重量，所以按力量排序，接下来就有点最长上升子序列的意思了，用dp[i]表示叠i只乌龟的最小重量，越小的话就好这也是显然的，那么我们就可以设sign表示最多有叠几只

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 6005;struct node{int wei,pow;
}arr[MAXN];
int dp[MAXN];bool cmp(const node a,const node b){return a.pow < b.pow;
}int main(){int n = 0;while (scanf("%d%d",&arr[n].wei,&arr[n].pow) != EOF)++n;sort(arr,arr+n,cmp);memset(dp,MAXN,sizeof(dp));int sign = 0;dp[0] = 0;for (int i = 0; i < n; i++)for (int j = sign; j >= 0; j--)if (dp[j] + arr[i].wei < arr[i].pow && dp[j+1] > dp[j]+arr[i].wei){dp[j+1] = dp[j] + arr[i].wei;sign = max(sign,j+1);}printf("%d\n",sign);return 0;
}

这篇关于UVA - 10154 Weights and Measures的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---