洛谷P3842题解

传送锚点

摸鱼环节

[TJOI2007] 线段

题目描述

在一个 \(n \times n\) 的平面上，在每一行中有一条线段，第 \(i\) 行的线段的左端点是\((i, L_{i})\)，右端点是\((i, R_{i})\)。

你从 \((1,1)\) 点出发，要求沿途走过所有的线段，最终到达 \((n,n)\) 点，且所走的路程长度要尽量短。

更具体一些说，你在任何时候只能选择向下走一步（行数增加 \(1\)）、向左走一步（列数减少 \(1\)）或是向右走一步（列数增加 \(1\)）。当然，由于你不能向上行走，因此在从任何一行向下走到另一行的时候，你必须保证已经走完本行的那条线段。

输入格式

第一行有一个整数 \(n\)。

以下 \(n\) 行，在第 \(i\) 行（总第 \((i+1)\) 行）的两个整数表示 \(L_i\) 和 \(R_i\)。

输出格式

仅包含一个整数，你选择的最短路程的长度。

样例 #1

样例输入 #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 \le 2 \times 10^4\)，\(1 \le L_i \le R_i \le n\)。

又是日常水题解的一天。
又是努力学oi的一天。咱们今天来切一道黄题(窝太菜了)。这道黄题也是很不人性化，从体面来看，感觉好像跟动态规划没啥毛关系，但是既然标签打了动态规划我们在训练动态规划，那就肯定先考虑动态规划。

正片开始

1.设计状态

考虑设计这道题的状态，很显然对于每一行都需要有个状态进行统计，而一条线段有左右两个端点，于是我们很容易的可以设出：

\(f[i][0/1]\)表示到达第i行的左端点0或右端点一的最小步数。

2.状态转移

设计完状态，接下来自然需要对状态进行转移，考虑当前状态的上一个状态不难得到：

\(f_{i,0}=min(f_{i-1,0}+abs(l_{i-1}-r_{i})+r_{i}-l_{i}+1 , f_{i-1,1}+abs(r_{i-1}-r_{i})+r_{i}-l_{i}+1)\)

同理易得

\(f_{i,1}=min(f_{i-1,0}+abs(l_{i-1}-l_{i})+r_{i}-l_{i}+1 , f_{i-1,1}+abs(r_{i-1}-l_{i})+r_{i}-l_{i}+1)\)

这样，状态转移就完成了。

code：

f[i][0]=min(f[i-1][0]+abs(l[i-1]-r[i])+r[i]-l[i]+1,f[i-1][1]+abs(r[i-1]-r[i])+r[i]-l[i]+1);
f[i][1]=min(f[i-1][0]+abs(l[i-1]-l[i])+r[i]-l[i]+1,f[i-1][1]+abs(r[i-1]-l[i])+r[i]-l[i]+1);

最后处理下结尾就ok了。

完整代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int l[N],r[N],f[N][3],n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>l[i]>>r[i];
    f[1][0]=r[1]+r[1]-l[1]+1;//需要经过这条线段
    f[1][1]=r[1]-1;
    for(int i=2;i<=n;i++)
    {
        f[i][0]=min(f[i-1][0]+abs(l[i-1]-r[i])+r[i]-l[i]+1,f[i-1][1]+abs(r[i-1]-r[i])+r[i]-l[i]+1);
        f[i][1]=min(f[i-1][0]+abs(l[i-1]-l[i])+r[i]-l[i]+1,f[i-1][1]+abs(r[i-1]-l[i])+r[i]-l[i]+1);
    }
    cout<<min(f[n][0]+abs(l[n]-n),f[n][1]+abs(r[n]-n));
    return 0;
}

完结。

个人主页

看完点赞，养成习惯

\(\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\)