POJ 1661 Help Jimmy LIS DP

时间:2022-01-26 05:48:43

http://poj.org/problem?id=1661

对板按高度排序后。

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 + ;
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][];
void work() {
// init();
int n, x, y, limit;
scanf("%d%d%d%d", &n, &x, &y, &limit);
for (int i = ; 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 = ;
memset(dp, 0x3f, sizeof dp);
dp[][].x = dp[][].x = x;
dp[][].h = dp[][].h = y;
dp[][].tim = dp[][].tim = ;
dp[][].cat = dp[][].cat = ;
for (int i = ; i <= n; ++i) {
dp[i][].cat = dp[i][].cat = ;
}
// cout << dp[3][1].cat << en
sort(a + , a + + n);
int ans = inf;
for (int i = ; i <= n; ++i) {
for (int j = ; j < i; ++j) {
if (dp[j][].h - a[i].h > limit) continue;
if (!dp[j][].cat) {
bool flag = true;
if (i == n) {
int cost = dp[j][].h + dp[j][].tim;
ans = min(ans, cost);
flag = false;
}
if (flag) {
if (dp[j][].x >= a[i].x && dp[j][].x <= a[i].y) {
dp[j][].cat = true;
int cost = dp[j][].x - a[i].x + dp[j][].h - a[i].h + dp[j][].tim;
if (dp[i][].tim > cost) {
dp[i][].tim = cost;
dp[i][].h = a[i].h;
dp[i][].x = a[i].x;
}
cost = a[i].y - dp[j][].x + dp[j][].h - a[i].h + dp[j][].tim;
if (dp[i][].tim > cost) {
dp[i][].tim = cost;
dp[i][].x = a[i].y;
dp[i][].h = a[i].h;
}
}
}
}
if (!dp[j][].cat) {
if (i == n) {
int cost = dp[j][].tim + dp[j][].h;
ans = min(ans, cost);
continue;
}
if (dp[j][].x >= a[i].x && dp[j][].x <= a[i].y) {
dp[j][].cat = true;
int cost = dp[j][].x - a[i].x + dp[j][].h - a[i].h + dp[j][].tim;
if (dp[i][].tim > cost) {
dp[i][].tim = cost;
dp[i][].x = a[i].x;
dp[i][].h = a[i].h;
}
cost = a[i].y - dp[j][].x + dp[j][].h - a[i].h + dp[j][].tim;
if (dp[i][].tim > cost) {
dp[i][].tim = cost;
dp[i][].h = a[i].h;
dp[i][].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 ;
}