题目描述
在一个 n*n 的平面上，在每一行中有一条线段，第 i 行的线段的左端点是(i, L(i))，右端点是(i, R(i))，其中 1 ≤ L(i) ≤ R(i) ≤ n。
你从(1, 1)点出发，要求沿途走过所有的线段，最终到达(n, n)点，且所走的路程长度要尽量短。
更具体一些说，你在任何时候只能选择向下走一步（行数增加 1）、向左走一步（列数减少 1）或是向右走一步（列数增加 1）。当然，由于你不能向上行走，因此在从任何一行向下走到另一行的时候，你必须保证已经走完本行的那条线段。
输入输出格式
输入格式：
输入文件的第一行有一个整数 n，以下 n 行，在第 i 行（总第(i+1)行）的两个整数表示
L(i)和 R(i)。
输出格式：
输出文件仅包含一个整数，你选择的最短路程的长度。
输入输出样例
输入样例#1：
6 2 6 3 4 1 3 1 2 3 6 4 5
输出样例#1：
24
说明
我们选择的路线是
(1,1) (1,6)
(2,6) (2, 3)
(3, 3) (3, 1)
(4, 1) (4, 2)
(5, 2) (5, 6)
(6, 6) (6, 4) (6, 6)不难计算得到，路程的总长度是 24。 100%的数据中，n ≤ 20 000。
ly的考试题就是刚，考场上我的记忆化搜索莫名其妙的wawawa，更加悲剧的是重启电脑没保存so啊啊啊啊啊
后来又打了一遍wa了一次就AC rp++
这道题fpy模拟+暴力dp搞出来的蒟蒻的我只会搜
设状态f[i][k]表示到走完第i行k（0左1右）位置所用最小步数
所以对于每层i我们有两大类
一 .k==0 （第i层左端点）
分三种情况
1.下一条线段右端点在i的左侧
2.下一条线段左端点在i的右侧
3.下一条线段左端点<i ，右端点>i
二 k==1 （第i层右端点）
分三种情况
1.下一条线段右端点在i的左侧
2.下一条线段左端点在i的右侧
3.下一条线段左端点<i ，右端点>i
初始化为+oo 边界即最后一层
搜索时不断取min即可
int dis(int x)
{
return R[x]-L[x];
}
int dfs(int i,int k)
{
if(f[i][k]!=f[0][0]) return f[i][k];
if(i==n)
{
if(k==0)return n-L[n];
if(k==1)return n-R[n];
}
int x_1,x_2,y_1,y_2;
x_1=L[i];
y_1=R[i];
x_2=L[i+1];
y_2=R[i+1];
if(k==0)
{
if(x_1>=y_2) f[i][k]=min(f[i][k],dfs(i+1,0)+1+x_1-x_2);
if(x_1<=x_2) f[i][k]=min(f[i][k],dfs(i+1,1)+1+y_2-x_1);
if(x_1<y_2&&x_1>x_2)
{
f[i][k]=min(f[i][k],dfs(i+1,0)+1+dis(i+1)+y_2-x_1);
f[i][k]=min(f[i][k],dfs(i+1,1)+1+dis(i+1)+x_1-x_2);
}
}
if(k==1)
{
if(y_1>=y_2) f[i][k]=min(f[i][k],dfs(i+1,0)+1+y_1-x_2);
if(y_1<=x_2) f[i][k]=min(f[i][k],dfs(i+1,1)+1+y_2-y_1);
if(x_2<y_1&&y_2>y_1)
{
f[i][k]=min(f[i][k],dfs(i+1,0)+1+y_2-y_1+dis(i+1));
f[i][k]=min(f[i][k],dfs(i+1,1)+1+dis(i+1)+y_1-x_2);
}
}
return f[i][k];
}
——————————————————————
memset(f,0x3f/3,sizeof(f));
ans=dfs(1,1);
ans+=R[1]-1;