POJ 1661 Help Jimmy LIS DP

对板按高度排序后。

dp[i][0]表示现在站在第i块板上，向左跑了，的状态，记录下时间和其他信息。

O(n^2)LIS；

唯一的麻烦就是，如果由第i块板---->第j块板，除了高度差会摔死之后，还可能会中间隔着一些板，使得它是去不了第j块的

所以用个vis标记下，如果i--->j中，vis[i]已经是true，表示第i块板已经被其他板截住了。判断一下就好。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
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;
}

View Code