Задача: вам дан набор досок с разной высотой и левым и правым концом. Джимми находится в каком-то начальном положении над всеми досками, и ему нужно запрыгнуть на доски одну за другой на землю. Существует максимальная разница в высоте (maxH), которую он может прыгать на каждом шагу, если следующая доска будет слишком низкой, Джимми умрет. Найдите минимальное время, необходимое для того, чтобы Джимми приземлился на землю, предположим, что он прыгает с постоянной скоростью со скоростью 1 единица в единицу времени.
Это задача динамического программирования. На каждой доске Джимми может спрыгнуть либо с левого, либо с правого конца. С любого конца Джимми должен прыгнуть на следующую доску (если есть доска ниже в пределах максимально допустимой разницы в высоте), и он выбирает, идти к левому или правому концу и снова прыгать, где Джимми оказывается в аналогичной ситуации прыжка.
Мы используем два массива LeftMinTIme и RightMinTime для хранения минимального времени, необходимого каждой доске для приземления с ее левого или правого конца. Мы можем рассматривать начальное положение Джимми как доску с одинаковыми левым и правым концом.
При восходящем подходе мы можем заполнить два массива от самой низкой доски к самой высокой. Если ниже нет доски и текущая высота больше, чем maxH, или падение на следующую доску больше, чем maxH, то минимальное время приземления для текущей доски бесконечно. В противном случае это меньшее значение между временем, необходимым для прыжка на следующую доску, и временем перехода от левого или правого конца следующей доски.
Коды:
// 0MS bottom up
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int n, x, y, maxH;
#define MAXN 1005
#define INF 99999999
int leftMinTime[MAXN];
int rightMinTime[MAXN];
struct bd{
int left, right, h;
bool operator < (const bd &B) const{
return h > B.h;
}
};
vector<bd> all;
int main(){
int t, cur_x, cur_y, j, i;
bd temp;
scanf("%d", &t);
while(t--){
scanf("%d%d%d%d", &n, &x, &y, &maxH);
// reset everything
memset(leftMinTime, 0, sizeof(leftMinTime));
memset(rightMinTime, 0, sizeof(rightMinTime));
all.clear();
all.push_back(bd{x, x, y});
for(int k=0; k<n; k++){
scanf("%d%d%d", &temp.left, &temp.right, &temp.h);
all.push_back(temp);
}
sort(all.begin(), all.end());
for(i=n; i>=0; i--){
cur_y = all[i].h;
//find board below left
cur_x = all[i].left;
for(j=i+1; j<=n; j++){
if(all[j].left <= cur_x && all[j].right >= cur_x)
break;
}
if(j>n){
//no board below
if(cur_y > maxH)
leftMinTime[i] = INF;
else
leftMinTime[i] = cur_y;
}
else{
if(cur_y - all[j].h > maxH)
leftMinTime[i] = INF;
else{
leftMinTime[i] = cur_y - all[j].h + min(
cur_x - all[j].left + leftMinTime[j],
all[j].right - cur_x + rightMinTime[j]);
}
}
//find board below right
cur_x = all[i].right;
for(j=i+1; j<=n; j++){
if(all[j].left <= cur_x && all[j].right >= cur_x){
break;
}
}
if(j>n){
if(cur_y > maxH)
rightMinTime[i] = INF;
else
rightMinTime[i] = cur_y;
}
else if(cur_y - all[j].h > maxH){
rightMinTime[i] = INF;
}
else{
rightMinTime[i] = cur_y - all[j].h + min(
cur_x - all[j].left + leftMinTime[j],
all[j].right - cur_x + rightMinTime[j]);
}
}
printf("%d\n", leftMinTime[0]);
}
}
Рекурсивный подход сверху вниз может быть более интуитивным. Мы пишем функцию с именем min_time, чтобы получить минимальное время, необходимое от доски для приземления. Мы используем логический параметр, чтобы решить, начинает ли Джимми с левого или правого конца этой доски. Затем находим следующую доску. Мы напрямую возвращаем бесконечность, если в пределах досягаемости нет следующей доски, или текущую высоту, если следующим шагом в досягаемости является земля (базовый случай). Затем мы снова вызываем рекурсивную функцию, чтобы найти минимальное время, необходимое от следующей доски до приземления. Затем мы прибавляем высоту от этой доски к следующей доске и расстояние до соответствующего конца следующей доски. Мы выбираем меньший из двух и обновляем наши массивы dp.
Коды:
//recursive function, 0MS
int min_time(int cur_bd, bool fromLeft){
int i, xx, yy=allB[cur_bd].h;
if(fromLeft && LeftMinTime[cur_bd]!=0)
return LeftMinTime[cur_bd];
if((!fromLeft) && RightMinTime[cur_bd]!=0)
return RightMinTime[cur_bd];
if(fromLeft)
xx = allB[cur_bd].left;
else
xx = allB[cur_bd].right;
i = cur_bd + 1;
while(i<=n){
if(allB[i].left<=xx && allB[i].right>=xx)
break;
i++;
}
if(i>n){
if(yy > maxH){
return INF;
}
else{
return allB[cur_bd].h;
}
}
else if(yy - allB[i].h > maxH){
return INF;
}
else{
int min_left_i = min_time(i, 1);
int min_right_i = min_time(i, 0);
int dh = yy - allB[i].h;
if(fromLeft){
LeftMinTime[cur_bd]=dh+min(allB[cur_bd].left-allB[i].left+min_left_i,
allB[i].right-allB[cur_bd].left+min_right_i);
return LeftMinTime[cur_bd];
}
else{
RightMinTime[cur_bd]=dh+min(allB[cur_bd].right-allB[i].left+min_left_i,
allB[i].right-allB[cur_bd].right+min_right_i);
return RightMinTime[cur_bd];
}
}
}
