题目链接：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;}

poj 1661 Help Jimmy（记忆化搜索）