关键词：
题目链接：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
" , gg + y);
}
return 0;
}
poj1661helpjimmy
传送门：http://poj.org/problem?id=1661解题思路：其实吧，不难就是细节有点麻烦。实现代码：#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;constintMAXN=20005;constintIN 查看详情
poj1661（helpjimmy）(代码片段)
HelpJimmyTimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 13669 Accepted: 4541Description"HelpJimmy"是在下图所示的场景上完成的游戏。 场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度... 查看详情
poj1661helpjimmy(二维dp)
题目链接：http://poj.org/problem?id=1661题目大意：如图包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。Jimmy老鼠在时刻0从高于所有平台的某处（高H处）开始下落，它的下落速度始终为1米/秒。当Jimmy... 查看详情
动规-poj-1661
http://poj.org/problem?id=1661HelpJimmy在同一竖直平面上，存在地面（高度为0，长度无限），以及若干个给定高度的水平平台（高度、左右端点给定）。现有Jimmy从给定点(x,y)跳下，下落的速度恒为1单位距离/单位时间。但下落的距离不... 查看详情
poj1661
题意HelpJimmy"是在下图所示的场景上完成的游戏。 场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。 Jimmy老鼠在时刻0从高于所有平台的某处开始下落，它的下落速度始终为1米/秒。当... 查看详情
poj2111milleniumleapcow(记忆化搜索）
DescriptionThecowshaverevisedtheirgameofleapcow.TheynowplayinthemiddleofahugepastureuponwhichtheyhavemarkedagridthatbearsaremarkableresemblancetoachessboardofNrowsandNcolumns(3<=N<=365). He 查看详情
poj1390blocks(记忆化搜索)
BlocksTimeLimit: 5000MS MemoryLimit: 65536KTotalSubmissions: 4318 Accepted: 1745DescriptionSomeofyoumayhaveplayedagamecalled‘Blocks‘.Therearenblocksinarow,eachboxhasacolo 查看详情
poj1661(kb12-mdp)
HelpJimmyDescription"HelpJimmy"是在下图所示的场景上完成的游戏。 场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。 Jimmy老鼠在时刻0从高于所有平台的某处开始下落，它的下落速度始终... 查看详情
poj1351numberoflocks（记忆化搜索）
题目链接：传送门思路：这道题是维基百科上面的记忆化搜索的例题。。。四维状态dp[maxn][5][2][5]分别表示第几根棒子，这根棒子的高度，是否达到题目的要求和使用不同棒子数。那么接下来就是状态转移了。。。要用到位运算... 查看详情
poj1179区间dp（记忆化搜索写法）有巨坑！
http://poj.org/problem?id=1179DescriptionPolygonisagameforoneplayerthatstartsonapolygonwithNvertices,liketheoneinFigure1,whereN=4.Eachvertexislabelledwithanintegerandeachedgeislabelledwitheitherthesym 查看详情
记忆化搜索||poj1088滑雪
...数那里走，问最远长度是多少*解法：每一点dfs搜索一遍记忆化搜索：http://blog.csdn.net/acmer_sly/article/details/53440798递归：求解的方法都是相同的（距离是周围的点最大值加一），假设已知周围点的距离则dd[i]=dfs(xx,yy)+1; 每一次递... 查看详情
poj1579functionrunfun记忆化搜索入门(代码片段)
题目传送门：http://poj.org/problem?id=1579FunctionRunFunTimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 20560 Accepted: 10325DescriptionWeallloverecursion!Don‘twe? 查看详情
poj1088滑雪（记忆化搜索）
滑雪TimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 92384 Accepted: 34948DescriptionMichael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次... 查看详情
poj1191棋盘切割（压缩dp+记忆化搜索）
一，题意：中文题二。分析：主要利用压缩dp与记忆化搜索思想三，代码：#include<iostream>#include<stdio.h>#include<string.h>#include<stdlib.h>#include<math.h>usingnamespacestd;constintBig=20000000;intMat[10] 查看详情
poj1088滑雪记忆化搜索
解析：状态d[i][j]代表r=i,c=j这个位置能滑的最大长度。深搜+备忘录#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>usingnamespacestd;constintmaxn=100+5;intR,C;inta[maxn][maxn];intd[m 查看详情
poj2704pascal'stravelsdfs记忆化搜索(代码片段)
题目传送门：http://poj.org/problem?id=2704Pascal‘sTravelsTimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 5535 Accepted: 2500DescriptionAnnxngameboardispopulatedwithinteg 查看详情
poj_1088_(dp)(记忆化搜索)
滑雪TimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 95792 Accepted: 36322DescriptionMichael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次... 查看详情
poj1088:滑雪（经典dp+记忆化搜索）
滑雪TimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 74996 Accepted: 27818DescriptionMichael喜欢滑雪百这并不奇怪，由于滑雪的确非常刺激。但是为了获得速度，滑的区域必须向下倾斜，并且当你滑到坡底，你不得不再... 查看详情