前言：余于模拟赛逢此题，欲解出，适脑小疾，未AC，觉此题甚版，作此解，以自省，又以尽Sam之愿。

题目

题目描述

数轴上有 $n$ 个检测点和 $n$ 把补给点。

每个检测点的坐标依次为 $a_1,a_2,\cdots,a_n$，每个补给点的坐标依次为 $b_1,b_2,\cdots,b_n$。

你一开始在数轴原点。到达补给点时，可以取走尚未取走的试剂盒；到达检测点时，可以消耗一个已经取得的试剂盒，完成该点的检测。每个检测点需要检测一次。

问完成全部检测所需的最小移动总距离。

输入格式

从文件 Hatsune.in 中读入。

第一行输入一个整数 $n$。

第二行输入 $n$ 个整数 $a_1,a_2,\cdots,a_n$，保证严格递增。

第三行输入 $n$ 个整数 $b_1,b_2,\cdots,b_n$，保证严格递增。

输出格式

输出至文件 Hatsune.out。

输出一行一个整数，代表移动的最小距离。

输入输出样例

输入 #1

4
1 6 7 12
3 5 10 11

输出 #1

21

一种移动方法为 $0\to 3\to 1\to 12\to 7$。

总距离为 $3+2+11+5=21$。

输入 #2

2
1 2
1 1000000000

输出 #2

1999999998

说明检测点与补给点可以位于同一坐标。

大样例

没搬受着

【数据范围】

本题采用捆绑测试。

测试点编号	$n\leq$	特殊性质
$1\sim 3$	$10$	无
$4\sim 6$	$20$
$7\sim 10$	$10^3$
$11\sim 12$	$10^5$	$a_i\geq b_i$
$13\sim 20$		无

对于 $100\%$ 的数据，$1\leq n\leq 10^5$，$1\leq a_i,b_i\leq 10^9$，$a_i<a_{i+1}$，$b_i<b_{i+1}$。

题解

我都不知道考场上我的脑袋去哪了

这种题一看就是先贪心再DP，因为显然不可贪心，如果DP直接做只能用状压，而状压是 $\Theta(2^n\cdot n)$ 的。

先看特殊性质，当 $a_i\geq b_i,i\in[1,n]$ 时，检测点在补给点后，一定可以先到补给点再到检测点，所以答案为 $a_n$。

再考虑一般情况，$\forall a_i\geq b_i$，检测点都在补给点后，都可以先到补给点再到检测点，因此这些检测点和补给都可以忽略。

为什么要忽略？

忽略无效贡献不仅方便DP转移，还减少代码分类讨论。

于是我们可以把剩余的点单独拎出来，设有 $m$ 个点满足 $a_i<b_i$，这些点的编号依次为 $k_1,k_2,\cdots,k_m$。

接着看样例。这个样例非常具有提示性，告诉我们要去补给点再回来完成一路的检测点，这时我们显然考虑DP：为了好优化成线性，DP的状态只能一维，所以考虑

• $dp_i$ 表示前 $i$ 个检测点都检测过，当前在第 $i$ 个检测点的位置，
• 或 $dp_i$ 表示前 $i$ 个补给点都走过，当前在第 $i$ 个补给点的位置。

每个都试一遍，发现第二个算答案困难，所以用第一个。

所以我们有：

$$dp_i=\begin{cases}\min_{j=0}^{i-1}\{dp_j+\underbrace{b_{k_i}-a_{k_j}}_{\text{从 $j$ 的检测点到 $i$ 的补给点}}+\underbrace{b_{k_i}-a_{k_{j+1}}+a_{k_i}-a_{k_{j+1}}}_{\text{从 $i$ 的补给点开始，把 $[j+1,i]$ 之间的所有的检测点检测，再回到 $i$ 的检测点}}\}&\text{if }i\geq1\\0&\text{if }i=0\end{cases}$$

最终答案为（建议先自己思考）：

$$\min\{dp_m+(\max\{a_n,b_n\}-a_{k_m}),\min_{i=0}^{m-1}dp_i+\underbrace{\max\{a_n,b_n\}-a_{k_i}}_{\text{从 $i$ 的检测点到最后一个点}}+\underbrace{\max\{a_n,b_n\}-a_{k_{i+1}}}_{\text{从最后一个点开始，把 $[i+1,n]$ 之间的所有的检测点检测}}\}$$

这样DP的转移是 $\Theta(n^2)$ 的，但容易把 $i$ 和 $j$ 的贡献拆开，

$$dp_i=2\cdot b_{k_i}+a_{k_i}+\min_{j=1}^{i-1}dp_j-a_{k_j}-2\cdot a_{k_{j+1}}$$

用一个变量维护一下 $\min_{j=1}^{i-1}dp_j-a_{k_j}-2\cdot a_{k_{j+1}}$ 就行。

代码

时间复杂度 $\Theta(n)$，空间复杂度 $\Theta(n)$。理论空间复杂度 $\Theta(1)$，但输入已经 $\Theta(n)$，所以没必要。

直接按题解写就行。

// 蜗蜗的巡检路线
#include <iostream>
#include <cstring>
using namespace std;

#define LL long long
const int N = 1e5 + 1023;
int n, k[N], m;
LL a[N], b[N], dp[N];

int main() {
    freopen("Hatsune.in", "r", stdin);
    freopen("Hatsune.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        if (a[i] < b[i]) k[++m] = i;
    }
    LL minv = -2 * a[k[1]];
    for (int i = 1; i <= m; i++) {
        dp[i] = 2 * b[k[i]] + a[k[i]] + minv;
        minv = min(minv, dp[i] - a[k[i]] - 2 * a[k[i + 1]]);
    }
    LL ans = dp[m] + max(a[n], b[n]) - a[k[m]];
    for (int i = 0; i <= m - 1; i++)
        ans = min(ans, dp[i] + max(a[n], b[n]) - a[k[i]] + max(a[n], b[n]) - a[k[i + 1]]);
    cout << ans << '\n';
    return 0;
}