E. Maximum Monogonosity

You are given an array aa of length nn and an array bb of length nn. The cost of a segment [l,r][l,r], 1≤l≤r≤n1≤l≤r≤n, is defined as |bl−ar|+|br−al||bl−ar|+|br−al|.

Recall that two segments [l1,r1][l1,r1], 1≤l1≤r1≤n1≤l1≤r1≤n, and [l2,r2][l2,r2], 1≤l2≤r2≤n1≤l2≤r2≤n, are non-intersecting if one of the following conditions is satisfied: r1<l2r1<l2 or r2<l1r2<l1.

The length of a segment [l,r][l,r], 1≤l≤r≤n1≤l≤r≤n, is defined as r−l+1r−l+1.

Find the maximum possible sum of costs of non-intersecting segments [lj,rj][lj,rj], 1≤lj≤rj≤n1≤lj≤rj≤n, whose total length is equal to kk.

Input

Each test consists of multiple test cases. The first line contains a single integer tt (1≤t≤1000)(1≤t≤1000) — the number of sets of input data. The description of the test cases follows.

The first line of each test case contains two integers nn and kk (1≤k≤n≤30001≤k≤n≤3000) — the length of array aa and the total length of segments.

The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (−109≤ai≤109−109≤ai≤109) — the elements of array aa.

The third line of each test case contains nn integers b1,b2,…,bnb1,b2,…,bn (−109≤bi≤109−109≤bi≤109) — the elements of array bb.

It is guaranteed that the sum of nn over all test case does not exceed 30003000.

Output

For each test case, output a single number — the maximum possible sum of costs of such segments.

我比赛时写的是o(nk^2) 的比较常规的转移

dp[n1][k1]=max(dp[n1−1][k1],dp[n1−l][k1−l]+f(n1−l+1,n1),1≤l≤k1)

看别人写之后才发现题目太妙了

首先我们不要把目光光顾着所有个区间，你去看方程的含义

其实化简出来有4中不同的方程

bl-ar+br-al

ar-bl+br-al

ar-bl+al-br

bl-ar+al-br

那bl，al来说有4种不同的状态(1,1),(1,-1),(-1,1),(-1,-1)

因为bl和ar相对应,al和bl相对应，那么br，br的状态恰好和ar，al的相反

所有整个方程有4种状态

那我们怎么知道要用哪种状态呢

我们用dp[4010][4010][5]来存储

dp[i][j][k]--》i表示当前到达第i位，j表示当前取j个元素,k(0~3)用状态压缩表示当第j个元素取al和bl的状态以及前面i-1位中取j-1个元素的最佳状态的和，k(4)表示当前取第i位取j个元素的最佳状态

因为我们上面说你知道ar,al的状态就能知道br,bl的状态：比如bl，al=（1，-1）则br，ar=（1，-1）

因为所有你通过枚举b就能知道当前的最大值

#include<iostream>
#include<algorithm>
#include<numeric>//accumulate(be,en,0)
#include<cstring>//rfind("string"),s.find(string,begin)!=s.npos,find_first _of(),find_last_of()
#include<string>//to_string(value),s.substr(int begin, int length);
#include<cstdio>
#include<cmath>
#include<vector>//res.erase(unique(res.begin(), res.end()), res.end()),reverse(q.begin(),q.end()),vector<int>().swap(at[mx])
#include<queue>//priority_queue(big)  /priority_queue<int, vector<int>, greater<int>> q(small)
#include<stack>
//#include<map>//unordered_map
#include<set>//iterator,insert(),erase(),lower(>=)/upper_bound(>)(value)/find()return end()
#include<unordered_map>
#include<unordered_set>
#include<bitset>//size,count(size of 1),reset(to 0),any(have 1?)
//#include<ext/pb_ds/assoc_container.hpp>//gp_hash_table
//#include<ext/pb_ds/hash_policy.hpp>
//using namespace __gnu_pbds;
#define int long long//__int128 2^127-1(GCC)
#define PII pair<int,int>
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f, N = 3000 + 5, mod = 1e9 + 7;
int dp[N][N][5];
signed main()
{ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);int T;cin >> T;while (T--) {int n, k;cin >> n >> k;vector<int>a(n), b(n);for (int& x : a) cin >> x;for (int& x : b) cin >> x;for (int i = 0; i < n + 1; i++) {for (int j = 0; j <= k; j++) {fill(dp[i][j], dp[i][j] + 5, -inf);//最开始初始化为负无穷}}dp[0][0][4] = 0;//第0位取0个的最佳状态是0for (int i = 0; i < n; i++) {//从0~n-1枚举位数for (int j = 0; j < k; j++) {//取j个转移到取j+1个for (int mask = 0; mask < 4; mask++) {//4a[l],b[l]个状态int s1 = (mask & 1 ? -1 : 1);//a[i]的状态int s2 = (mask & 2 ? -1 : 1);//b[i]的状态dp[i][j + 1][mask] = max(dp[i][j + 1][mask], dp[i][j][4] + s1 * a[i] + s2 * b[i]);
//第i位取j+1个是从第i位取j个的最佳状态转移过去的}}for (int j = 0; j <= k; j++) {//当前取j个for (int mask = 0; mask < 4; mask++) {//枚举b[r],a[r]的状态int s1 = (mask & 1 ? -1 : 1);//b[r]int s2 = (mask & 2 ? -1 : 1);//a[r]dp[i][j][4] = max(dp[i][j][4], dp[i][j][mask] - s2 * a[i] - s1 * b[i]);
//因为mask的状态只有a[l],b[l]是不完整的最大值，我们从不完整的加上b[r],a[r]就成了完整的状态就
//是转移到dp[i][j][4]中表示前i为取j个的最大值if (j != k) dp[i + 1][j + 1][mask] = dp[i][j][mask];
//如果取的个数不到k个的话，不完整的状态就可以继续往下传递}dp[i + 1][j][4] = max(dp[i + 1][j][4], dp[i][j][4]);
//最后前i个取j个的最大值转移到前i+1个取j个的最大值}}cout << dp[n][k][4] << '\n';
//输出前n个取k个的最大值}
}