本文主要是介绍uva 10154 DP 叠乌龟，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给你几只乌龟，每只乌龟有自身的重量和力量。
每只乌龟的力量可以承受自身体重和在其上的几只乌龟的体重和内。
问最多能叠放几只乌龟。
解析：
先将乌龟按力量从小到大排列。
然后dp的时候从前往后叠，状态转移方程：
dp[i][j] = dp[i - 1][j];if (dp[i - 1][j - 1] != inf && dp[i - 1][j - 1] <= t[i].strength - t[i].weight){dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + t[i].weight);}代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long longusing namespace std;
const int maxn = 5607 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double pi = 4 * atan(1.0);
const double ee = exp(1.0);struct Turtle
{int weight;int strength;
} t[maxn];bool cmp(Turtle a, Turtle b)
{return a.strength < b.strength;
}int dp[maxn][maxn];int main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALint n = 1;int x, y;while (scanf("%d%d", &x, &y) != EOF){t[n].weight = x;t[n].strength = y;n++;}n--;sort(t + 1, t + n + 1, cmp);for (int i = 0; i <= n; i++){dp[i][0] = 0;for (int j = 1; j <= n; j++){dp[i][j] = inf;}}for (int i = 1; i <= n; i++){for (int j = 1; j <= i; j++){dp[i][j] = dp[i - 1][j];if (dp[i - 1][j - 1] != inf && dp[i - 1][j - 1] <= t[i].strength - t[i].weight){dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + t[i].weight);}}}for (int i = n; i >= 1; i--){if (dp[n][i] != inf){printf("%d\n", i);break;}}return 0;
}
这篇关于uva 10154 DP 叠乌龟的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
