蠻麻煩的一個(gè)題 但是說白了 也就是一個(gè)類似最長上升子序列的東西（可能跳轉(zhuǎn)的跨度大了些） 從底部往上逐層DP,每一層有兩個(gè)狀態(tài) 分別求之。小結(jié)一下吧 做了這么多動(dòng)態(tài)規(guī)劃題 我發(fā)現(xiàn) 動(dòng)態(tài)規(guī)劃的實(shí)質(zhì) 居然是窮舉 ，囧啊，或者更確切的來說是 帶記憶化的窮舉！存儲(chǔ)加遞歸應(yīng)該還是欠妥的，因?yàn)楫吘褂辛俗顑?yōu)子結(jié)構(gòu)以后 后效狀態(tài)便消除了，而且也并沒有揭示出DP解法的全局性（如果用更宏觀的視角來看待它），即它在求得答案的同時(shí)，也獲得了其他更多的信息，這些信息不是冗余（redundant 恩GRE高頻詞），形象的說 應(yīng)該是在DP之路上，為答案作出貢獻(xiàn)的朋友，如果我們換一個(gè)問題，也許它們也就成了答案。
對了，補(bǔ)充一下，我覺得這個(gè)題最重要的地方在于，當(dāng)你找到了一塊板剛好能接住從左側(cè)下降的你時(shí)，你便不用再考慮更下層的板了，因?yàn)槟悴豢赡艽Γò澹?
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
#define INF 999999999
struct node
{
int x1;
int x2;
int h;
bool operator <(node other)
{
return h>other.h;
}
}a[1005];
int dp[1001][2];
int n,x,y,mh;
int main()
{
int t;
int i,j,k;
scanf("%d",&t);
for(k=1;k<=t;k++)
{
scanf("%d%d%d%d",&n,&x,&y,&mh);
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i].x1,&a[i].x2,&a[i].h);
dp[i][0]=dp[i][1]=INF;
}
dp[n+1][0]=dp[n+1][1]=0;
a[n+1].x1=-INF;
a[n+1].x2=INF;
sort(a+1,a+1+n);
for(i=n;i>=1;i--)
{
bool l=false;
bool r=false;
for(j=i+1;j<=n+1;j++)
{
if(a[i].h-a[j].h>mh)
break;
if(!l&&a[i].x1>=a[j].x1&&a[i].x1<=a[j].x2)
{
if(j==n+1) dp[i][0]=0;
else
{
dp[i][0]=min(dp[i][0],dp[j][0]+a[i].x1-a[j].x1);
dp[i][0]=min(dp[i][0],dp[j][1]+a[j].x2-a[i].x1);
l=true;
}
}
if(!r&&a[i].x2>=a[j].x1&&a[i].x2<=a[j].x2)
{
if(j==n+1) dp[i][1]=0;
else
{
dp[i][1]=min(dp[i][1],dp[j][0]+a[i].x2-a[j].x1);
dp[i][1]=min(dp[i][1],dp[j][1]+a[j].x2-a[i].x2);
r=true;
}
}
}
}
int res=0;
for(i=1;i<=n+1;i++)
{
if(a[i].x1<=x&&x<=a[i].x2&&y>=a[i].h)
{
res=min(x-a[i].x1+dp[i][0],a[i].x2-x+dp[i][1]);
break;
}
}
res+=y;
printf("%d\n",res);
}
return 0;
}