Codeforces Round 935 (Div. 3) - D. Seraphim the Owl （动态规划）

大家排成 n 人的队列，从 i=1 号开始，向猫头鹰谢拉菲姆请教生命的意义。不幸的是，基里尔当时正忙着为这问题编写传说，所以他来得晚了一些，站在了 n 这个人之后，排在了队伍的最后。基里尔对这种情况完全不满意，于是他决定贿赂一些排在他前面的人。

对于队列中的第 $i$ 个人，基里尔知道两个值： $a_i$ 和 $b_i$ 。如果此刻基里尔站在位置 $i$ 上，那么他可以选择任意一个位置 $j$ ，比如 $j < i$ 并与位置 $j$ 的人交换位置。在这种情况下，基里尔需要支付他 $a_j$ 个金币。而对于 $k$ 中的每一个 $j < k < i$ ，基里尔都要向位置 $k$ 的人支付 $b_k$ 个金币。基里尔可以任意多次执行这个操作。

基里尔很节俭，所以他想花尽可能少的硬币，但是他又不想等太久，所以基里尔认为他应该排在 $m$ 的第一位。

请帮助基里尔确定，为了不等太久，他最少需要花费多少金币。

输入

每个测试由几组输入数据组成。第一行包含一个整数 $t ( 1≤t≤10^4 )$ - 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m (1 \leq m \leq n \leq 200000)$ –分别是除基里尔之外的队列人数和基里尔最终位置的最大允许值。

第二行包含 $n$ 个整数 $a_1,a_2,…,a_n$ ，用空格分隔 $1≤a_i≤10^9 )$ 。

第三行包含 $n$ 个整数 $b_1,b_2,…,b_n$ ，以空格分隔 $1≤b_i≤10^9 )$ 。

保证所有测试用例中 $n$ 的值之和不超过 $2⋅10^5$ 。

输出

对于每个测试用例，输出一个整数 ——Kirill 需要花费的最少金币数。

Example

input

4
4 2
7 3 6 9
4 3 8 5
6 2
6 9 7 1 8 3
5 8 8 1 4 1
7 7
7 2 9 2 6 5 9
9 1 10 7 1 4 9
2 1
2 3
1 1

output

首先读懂题，如果我们现在在队尾位置 $（ n + 1 ）$ 想要去 $c$ 位置，那么我们要花费 $\sum\limits^{c - 1}_{i = n}b[i] + a[c]$ 的钱。

对于这题我觉得DP的方法更容易理解，参考了洛谷RailgunZzzz大佬的题解，%%%。

这里开不了二维dp数组，因为范围太大，所以考虑用一维的。

这里用f[i]来代表从队尾到 $j$ 位置的所有走法的最小花费。

这里首先分析，如果我们要从 $j$ 点走到 $i$ 点，那么就要花费 $\sum\limits_{k = n}^{j - 1} - \sum\limits_{k = n}^{i}$ ，注意这里是从后往前走，不要搞反了。

对于那些求和符号，我们可以把 $b$ 数组维护成一个前缀和数组。
但是如果我们枚举两个点就会导致超时，所以我们观察一下这个式子，尝试用数学方式优化他。

$f [i] = min (f [j] + b [j - 1] - b [i] + a [i])$

在这个式子中关于j的项仅有 $f [j] + b [j - 1]$ ，因为我们是由上一个 $j$ 状态转移到了 $i$ 状态， $- b [i] + a [i]$ 并不影响对于最小值的选取，所以可以把关于 $i$ 的项提出来。

那么我们就得到了式子： $f [i] = min (f [j] + b [j - 1]) - b [i] + a [i]$

这时 $min (f [j] + b [j - 1])$ 就可以使用一个变量来维护，这样就保持到了 $O (N)$ 的时间复杂度。
只需要在循环中维护一个变量不断更新就能取到 $min (f [n] + b [n - 1], f [n - 1] + b [n - 2], f [n - 2] + b [n - 3], ......)$ 。

注意要开long long，不然会爆int。

代码：

#include<iostream>
#include<cmath>
#include<cstring>
#pragma warning (disable : 4996)
using namespace std;
const int N = 2e5 + 10;


int a[N];
long long b[N];
long long f[N];
int n, m;

int main() {
	int T; cin >> T;
	while (T--) {
		memset(f, 0, sizeof f);	//每次需要初始化，不然wa
		memset(b, 0, sizeof b);
		memset(a, 0, sizeof a);

		scanf("%d%d", &n, &m);

		for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
		for (int i = 1; i <= n; i++) {
			scanf("%d", &b[i]);
			b[i] += b[i - 1];	//转化为前缀和数组
		}

		long long mm = b[n];	//维护最小值最好也开个long long

		for (int j = n; j >= 1; j--) {	//状态转移过程
			f[j] = mm - b[j] + a[j];
			mm = min(mm, f[j] + b[j - 1]);
			//整个过程来看，mm取到了
			//min(f[n] + b[n-1] , f[n-1] + b[n-2] , f[n-2] + b[n-3],......)
		}

		long long res = 1e18;	//注意取答案一定要开Longlong初始化为1e18，不然会出错

		//注意这里为什么遍历1~m取最小值，因为题目要求最少换到m
		//所以我们换到m的前面也是没问题的，如果能用更小的花费为什么不换呢
		for (int i = 1; i <= m; i++)res = min(res, f[i]);
		cout << res << endl;
	}
	return 0;
}