[TJOI2007] 线段

# [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$。

//P3842 [TJOI2007] 线段
//贪心(58分)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e4+10;
int n,m,res,a[N],l[N],r[N],last;
bool vis[N],now;
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>l[i]>>r[i];
    for(int i=1;i<=n;i++){
            if(last>l[i]&&r[i]>last) res+=(last-l[i])*2,res+=(r[i]-last),last=r[i];
            else if(r[i]<=last) res+=(last-l[i]),last=l[i];
            else res+=(r[i]-last),last=r[i];
    }
    if(last!=r[n]) res+=abs(last-n);
    cout<<res+n-1;
    return 0;
}
//状态机:
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2e4+10;
int n,m,res,f[2][N],l[N],r[N],len[N],num;
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>l[i]>>r[i],len[i]=r[i]-l[i];
    f[0][1]=r[1]-1+len[1],f[1][1]=r[1]-1;
    for(int i=2;i<=n;i++){
        f[0][i]=min(f[0][i-1]+abs(r[i]-l[i-1]),f[1][i-1]+abs(r[i]-r[i-1]))+len[i]+1;
        f[1][i]=min(f[0][i-1]+abs(l[i]-l[i-1]),f[1][i-1]+abs(r[i-1]-l[i]))+len[i]+1;
    }
    cout<<min(f[0][n],f[1][n])+abs(n-r[n])<<endl;
    return 0;
}