本文共 2714 字，大约阅读时间需要 9 分钟。
对板按高度排序后。
dp[i][0]表示现在站在第i块板上，向左跑了，的状态，记录下时间和其他信息。
O(n^2)LIS；
唯一的麻烦就是，如果由第i块板---->第j块板，除了高度差会摔死之后，还可能会中间隔着一些板，使得它是去不了第j块的
所以用个vis标记下，如果i--->j中，vis[i]已经是true，表示第i块板已经被其他板截住了。判断一下就好。
#include #include #include #include #include #include #define IOS ios::sync_with_stdio(false)using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include #include #include #include #include #include #include const int maxn = 1e3 + 20;struct node { int x, y, h; bool operator < (const struct node & rhs) const { if (h != rhs.h) return h > rhs.h; else if (x != rhs.x) return x < rhs.x; else return y < rhs.y; }} a[maxn];struct DP { int x, h, tim; int cat;} dp[maxn][2];void work() {// init(); int n, x, y, limit; scanf("%d%d%d%d", &n, &x, &y, &limit); for (int i = 1; i <= n; ++i) { scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].h); } n++; a[n].x = -inf; a[n].y = inf; a[n].h = 0; memset(dp, 0x3f, sizeof dp); dp[0][0].x = dp[0][1].x = x; dp[0][0].h = dp[0][1].h = y; dp[0][0].tim = dp[0][1].tim = 0; dp[0][0].cat = dp[0][1].cat = 0; for (int i = 0; i <= n; ++i) { dp[i][0].cat = dp[i][1].cat = 0; }// cout << dp[3][1].cat << en sort(a + 1, a + 1 + n); int ans = inf; for (int i = 1; i <= n; ++i) { for (int j = 0; j < i; ++j) { if (dp[j][0].h - a[i].h > limit) continue; if (!dp[j][0].cat) { bool flag = true; if (i == n) { int cost = dp[j][0].h + dp[j][0].tim; ans = min(ans, cost); flag = false; } if (flag) { if (dp[j][0].x >= a[i].x && dp[j][0].x <= a[i].y) { dp[j][0].cat = true; int cost = dp[j][0].x - a[i].x + dp[j][0].h - a[i].h + dp[j][0].tim; if (dp[i][0].tim > cost) { dp[i][0].tim = cost; dp[i][0].h = a[i].h; dp[i][0].x = a[i].x; } cost = a[i].y - dp[j][0].x + dp[j][0].h - a[i].h + dp[j][0].tim; if (dp[i][1].tim > cost) { dp[i][1].tim = cost; dp[i][1].x = a[i].y; dp[i][1].h = a[i].h; } } } } if (!dp[j][1].cat) { if (i == n) { int cost = dp[j][1].tim + dp[j][1].h; ans = min(ans, cost); continue; } if (dp[j][1].x >= a[i].x && dp[j][1].x <= a[i].y) { dp[j][1].cat = true; int cost = dp[j][1].x - a[i].x + dp[j][1].h - a[i].h + dp[j][1].tim; if (dp[i][0].tim > cost) { dp[i][0].tim = cost; dp[i][0].x = a[i].x; dp[i][0].h = a[i].h; } cost = a[i].y - dp[j][1].x + dp[j][1].h - a[i].h + dp[j][1].tim; if (dp[i][1].tim > cost) { dp[i][1].tim = cost; dp[i][1].h = a[i].h; dp[i][1].x = a[i].y; } } } } }// cout << dp[3][1].cat << endl; cout << ans << endl;}int main() {#ifdef local freopen("data.txt", "r", stdin);// freopen("data.txt", "w", stdout);#endif int g; cin >> g; while (g--) work(); return 0;}
转载于:https://www.cnblogs.com/liuweimingcprogram/p/6221511.html
