题解 P3842 【[TJOI2007]线段】

pzc2004 · 2019-08-14 13:57:59 · 题解

题目传送门

UPD:2021/6/19 修改了一个错误

这题就是一个简单的 dp 题。

用 f_{i,0} 表示走到第 i 行的线段的左端点的最少步数，用 f_{i,1} 表示走到第 i 行的线段的右端点的最少步数。

那么可以得到 f_{1,1}=dis(1,r_1),f_{1,0}=dis(1,r_1)+dis(r_1,l_1)（dis 表示距离）。

显然 f_{i,0} 只能从 f_{i-1,0} 和 f_{i-1,1} 转移过来，如果是从 f_{i-1,0} 转移过来，显然需要从第 i-1 行的线段的左端点先往下移一格，再移到第i行的线段的右端点，再移到左端点；如果是从 f_{i-1,0} 转移过来，显然需要从第 i-1 行的线段的右端点先往下移一格，再移到第 i 行的线段的右端点，再移到左端点。

那么就可以得到：

同理，对于 f_{i,1} 也是一样：

然后就可以愉快的AC了。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[20001][2],f[20001][2];//a[i][0]表示l[i],a[i][1]表示r[i]
int dis(int a,int b)//计算距离
{
    return abs(a-b);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i][0],&a[i][1]);
    f[1][0]=dis(a[1][1],1)+dis(a[1][1],a[1][0]);
    f[1][1]=dis(a[1][1],1);
    for(int i=2;i<=n;i++)//状态转移
    {
        f[i][0]=min(f[i-1][0]+dis(a[i-1][0],a[i][1])+dis(a[i][1],a[i][0]),f[i-1][1]+dis(a[i-1][1],a[i][1])+dis(a[i][1],a[i][0]))+1;
        f[i][1]=min(f[i-1][0]+dis(a[i-1][0],a[i][0])+dis(a[i][0],a[i][1]),f[i-1][1]+dis(a[i-1][1],a[i][0])+dis(a[i][0],a[i][1]))+1;
    }
    printf("%d",min(f[n][0]+dis(a[n][0],n),f[n][1]+dis(a[n][1],n)));//最后的答案还要加上到(n,n)的距离
}