POJ – 1661 Help Jimmy

题目链接

f[i][0]:从i平台左端跳下到地面的最短时间(不包括竖直距离)
f[i][1]:从j平台右端跳下到地面的最短时间(不包括竖直距离)

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9;
struct level {
  int x1, x2, h;
} a[1005];

bool cmp(level a, level b) { return a.h > b.h; }

long long f[1005][2];

int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int T, N, X, Y, MAX;
  cin >> T;
  while (T--) {
    cin >> N >> X >> Y >> MAX;
    for (int i = 1; i <= N; i++) {
      cin >> a[i].x1 >> a[i].x2 >> a[i].h;
    }
    //起点
    a[0].x1 = X;
    a[0].x2 = X;
    a[0].h = Y;
    //地面
    a[N + 1].x1 = -INF;
    a[N + 1].x2 = INF;
    a[N + 1].h = 0;
    sort(a + 1, a + 1 + N, cmp);  //从高到低排序
    for (int i = N; i >= 0; --i) {
      int j;
      //从i的左端跳下
      for (j = i + 1; j <= N + 1; ++j) {
        if (a[j].x1 <= a[i].x1 && a[i].x1 <= a[j].x2) {
          break;
        }
      }
      if (j == N + 1) {
        if (a[i].h <= MAX)
          f[i][0] = 0;
        else
          f[i][0] = INF;
      } else {
        if (a[i].h - a[j].h <= MAX) {
          int t1 = a[i].x1 - a[j].x1 + f[j][0];
          int t2 = a[j].x2 - a[i].x1 + f[j][1];
          f[i][0] = min(t1, t2);
        } else
          f[i][0] = INF;
      }
      //从i的右端跳下
      for (j = i + 1; j <= N + 1; ++j) {
        if (a[j].x1 <= a[i].x2 && a[i].x2 <= a[j].x2) {
          break;
        }
      }
      if (j == N + 1) {
        if (a[i].h <= MAX)
          f[i][1] = 0;
        else
          f[i][1] = INF;
      } else {
        if (a[i].h - a[j].h <= MAX) {
          int t1 = a[i].x2 - a[j].x1 + f[j][0];
          int t2 = a[j].x2 - a[i].x2 + f[j][1];
          f[i][1] = min(t1, t2);
        } else
          f[i][1] = INF;
      }
    }
    cout << f[0][0] + Y << endl;
  }
  return 0;
}