POJ 1661 Help Jimmy ——（记忆化搜索）

　　典型的记忆化搜索问题，dfs一遍即可。但是不知道WA在哪里了= =，一直都没找出错误。因为思路是很简单的，肯定是哪里写挫了，因此不再继续追究了。

　　WA的代码如下，希望日后有一天能找出错误= =：

————————————————灵光一闪的分界线——————————————————

　　在写博客的时候突然灵光一闪，想到了错在哪里了= =。总的来说还是考虑问题不周导致的。AC代码如下：

  1 #include <stdio.h>
  2 #include <algorithm>
  3 #include <string.h>
  4 using namespace std;
  5 const int N = 1000 + 5;
  6 const int inf = 0x3f3f3f3f;
  7 
  8 int n,x,y,limit;
  9 int left[N],right[N],h[N];
 10 int L_nxt[N],R_nxt[N];
 11 void find(int u)
 12 {
 13     int L = -1, R = -1;
 14     for(int i=1;i<=n;i++)
 15     {
 16         if(u == i || h[i] >= h[u]) continue;
 17         if(left[u] >= left[i] && left[u] <= right[i])
 18         {
 19             if(L == -1) L = i;
 20             else if(h[i] > h[L]) L = i;
 21         }
 22         if(right[u] >= left[i] && right[u] <= right[i])
 23         {
 24             if(R == -1) R = i;
 25             else if(h[i] > h[R]) R = i;
 26         }
 27     }
 28     if(L == -1)
 29     {
 30         if(h[u] > limit) L_nxt[u] = -2; // 表示不能往这个方向跳下
 31         else L_nxt[u] = -1; // 表示可以到地面
 32     }
 33     else if(h[u] - h[L] > limit) L_nxt[u] = -2;
 34     else L_nxt[u] = L;
 35     
 36     if(R == -1)
 37     {
 38         if(h[u] > limit) R_nxt[u] = -2; // 表示不能往这个方向跳下
 39         else R_nxt[u] = -1; // 表示可以到地面
 40     }
 41     else if(h[u] - h[R] > limit) R_nxt[u] = -2;
 42     else R_nxt[u] = R;
 43 }
 44 
 45 struct node
 46 {
 47     int L, R;
 48     void init() {L = R = inf;}
 49 };
 50 bool vis[N];
 51 node dp[N];
 52 node dfs(int u)
 53 {
 54     if(vis[u]) return dp[u];
 55     vis[u] = 1;
 56     node ans; ans.init();
 57     if(L_nxt[u] != -2)
 58     {
 59         if(L_nxt[u] == -1) ans.L = h[u];
 60         else
 61         {
 62             node temp = dfs(L_nxt[u]);
 63             ans.L = min(ans.L, h[u] - h[L_nxt[u]] + min(left[u] - left[L_nxt[u]] + temp.L, right[L_nxt[u]] - left[u] + temp.R));
 64         }
 65     }
 66     
 67     if(R_nxt[u] != -2)
 68     {
 69         if(R_nxt[u] == -1) ans.R = h[u];
 70         else
 71         {
 72             node temp = dfs(R_nxt[u]);
 73             ans.R = min(ans.R, h[u] - h[R_nxt[u]] + min(right[u] - left[R_nxt[u]] + temp.L, right[R_nxt[u]] - right[u] + temp.R));
 74         }
 75     }
 76     return dp[u] = ans;
 77 }
 78 
 79 int main()
 80 {
 81     int T; scanf("%d",&T);
 82     while(T--)
 83     {
 84         scanf("%d%d%d%d",&n,&x,&y,&limit);
 85         for(int i=1;i<=n;i++) scanf("%d%d%d",left+i,right+i,h+i);
 86         for(int i=1;i<=n;i++) find(i);
 87         memset(vis,false,sizeof vis);
 88 
 89         int root = -1;
 90         for(int i=1;i<=n;i++)
 91         {
 92             if(x >= left[i] && x <= right[i])
 93             {
 94                 if(root == -1) root = i;
 95                 else if(h[root] < h[i]) root = i;
 96             }
 97         }
 98         // root为-1的话dfs会出错的，因此要特判
 99         if(root == -1) {printf("%d
",y); continue;}
100         
101         dfs(root);
102         int ans = y - h[root] + min(x - left[root] + dp[root].L, right[root] - x + dp[root].R);
103         printf("%d
",ans);
104     }
105     return 0;
106 }