习题：烽火传递（DP+单调队列）

题目描述

有 $n$ 座城市排成一条直线，第 $i$ 座城市的高度为 $h_i$。现在要在城市之间传递一份文件，传递的顺序与城市的高度相同。即若 $i<j$ 且 $h_i<h_j$，则文件必须先从第 $i$ 座城市传递到第 $j$ 座城市，再从第 $j$ 座城市传递到第 $k$ 座城市。

每座城市传递文件的代价为 $c_i$，即从第 $i$ 座城市传递文件到第 $j$ 座城市需要花费 $c_i$ 的代价。现在要求从第 $1$ 座城市传递文件到第 $n$ 座城市，每座城市都必须传递文件，且总代价最小。

输入格式

第一行包含整数 $n$。

第二行包含 $n$ 个整数 $h_1,h_2,\dots,h_n$。

第三行包含 $n$ 个整数 $c_1,c_2,\dots,c_n$。

输出格式

输出一个整数，表示总代价最小值。

数据范围

$1≤n≤10^6,$
$1≤h_i,c_i≤10^3$

输入样例1

5
3 2 4 1 5
4 5 2 1 3

输出样例1

12

输入样例2

5
5 4 3 2 1
5 4 3 2 1

输出样例2

15

算法1

(dp + 单调队列) $O(n)$

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码