题目链接：http://poj.org/problem?id=1661
一道还可以的记忆化搜索题，主要是要想到如何设dp，记忆化搜索是避免递归过程中的重复求值，所以要得到dp必须知道如何递归
由于这是个可以左右移动的所以递归过程肯定设计左右所以dp的一维为从左边下或者从右边下，而且和层数有关所以另一维为层数
于是便可以得到dp[count][flag],flag=1表示count层从左边下要多久,flag=0表示count层从右边下要多久。然后就是dfs的递归
过程
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int M = 2e4 + 10 , MM = 6e4 + 10;
int n , x , y , MAX;
int dp[1010][2];
struct TnT {
int sta , ed , h;
}s[1010];
bool cmp(TnT a , TnT b) {
return a.h > b.h;
}
int dfs(int count , int flag) {
if(count == n) {
return 0;
}
int ans = MM;
if(dp[count][flag] != -1) {
return dp[count][flag];
}
int temp = count;
for(int i = count + 1 ; i <= n ; i++) {
temp = i;
if(s[count].h - s[i].h <= MAX) {
if(flag == 1) {
if(s[count].ed <= s[i].ed && s[count].ed >= s[i].sta) {
ans = min(dfs(i , flag) + s[i].ed - s[count].ed , dfs(i , 1 - flag) + s[count].ed - s[i].sta);
break;
}
}
if(flag == 0) {
if(s[count].sta <= s[i].ed && s[count].sta >= s[i].sta) {
ans = min(dfs(i , flag) + s[count].sta - s[i].sta , dfs(i , 1 - flag) + s[i].ed - s[count].sta);
break;
}
}
}
else {
break;
}
}
if(ans == MM) {
if(temp == n) {
if(s[count].h > MAX) {
dp[count][flag] = ans;
return ans;
}
else {
ans = 0;
dp[count][flag] = ans;
return ans;
}
}
dp[count][flag] = ans;
return ans;
}
else {
dp[count][flag] = ans;
return ans;
}
}
int main() {
int t;
scanf("%d" , &t);
while(t--) {
scanf("%d%d%d%d" , &n , &x , &y , &MAX);
for(int i = 1 ; i <= n ; i++) {
scanf("%d%d%d" , &s[i].sta , &s[i].ed , &s[i].h);
}
sort(s + 1 , s + n + 1 , cmp);
s[0].sta = s[0].ed = x , s[0].h = y;
s[n + 1].sta = -M , s[n + 1].ed = M , s[n + 1].h = 0;
memset(dp , -1 , sizeof(dp));
int gg = dfs(0 , 0);
gg = min(dfs(0 , 1) , gg);
printf("%d\n" , gg + y);
}
return 0;
}