$$\mathrm{城市交通}$$

题目链接：$\mathrm{j}\mathrm{z}\mathrm{o}\mathrm{j}1749$

题目

编号为 $1\sim n$ 的 $n$ 个城市，每个城市有两个权值 $A_i$ 和 $B_i$ 。

对于两个城市 $i$ 和 $j$ ， $i$ 可到 $j$ 当且仅当 $j>i$ ，而费用为 $(j-i)\ast A_i+B_j$ 。

求从城市 $1$ 到城市 $n$ 的最小费用。

输入

第一行一个正整数 $n$ 。

第二行 $n$ 个正整数，第 $i$ 个表示 $A_i$ 。

第三行 $n$ 个正整数，第 $i$ 个表示 $B_i$。

输出

一个数，表示最小的费用。

样例输入

4
2 9 5 4
9 1 2 2

样例输出

8

数据范围

对于 $20\%$ 的数据， $1<=n<=100$ ；
对于 $50\%$ 的数据， $1<=n<=3000$ ；
对于 $100\%$ 的数据， $1<=n<=100000，1<=A_i,B_i<=10^9$ 。

思路

这道题用dp来做。

设 $f[i]$ 为从 $1$ 走到 $i$ 最少的体力。
那就从前面可以作为起点的所有点作为开始走的点，找到费用最小的一个。

最后输出 $f[n]$ 就可以了。

代码

#include<cstdio>
#include<cstring>
#define ll long long
#define min(x, y) (x) < (y) ? (x) : (y)

using namespace std;

int n, use[100001], k;
ll a[100001], b[100001], f[100001];
bool yes;

int main() {
	scanf("%d", &n);//读入
	for (int i = 1; i <= n; i++)
		scanf("%lld", &a[i]);//读入
	for (int i = 1; i <= n; i++)
		scanf("%lld", &b[i]);//读入
	
	memset(f, 0x7f, sizeof(f));//初始化
	f[1] = 0;
	use[++k] = 1;
	for (int i = 2; i <= n; i++) {
		yes = 1;
		for (int j = 1; j <= k; j++) {
			f[i] = min(f[i], f[use[j]] + a[use[j]] * (i - use[j]) + b[i]);//从哪里走
			if (a[i] > a[use[j]] && b[i] > b[use[j]]) yes = 0;
		}
		if (yes) use[++k] = i;//可以作为起点
	}
	
	printf("%lld", f[n]);//输出
	
	return 0;
}