原题传送门：Problem - D - Codeforces

题目大意

有 T 个测试用例。

每个用例，有一个 N 表示题目的数量，每个题有个难度（Ci = 2 ^ i）即2的i次方。

接下来两行分别是题目标签tag和题目分数s。

初始 IQ 为 0 ，每次做的题难度必须大于当前的IQ，刚做完题目i，如果 |ci - cj| > IQ 且 tag[i] != tag[j] 现在去做题目j，做完之后IQ = |ci - cj|。

求可以获得的最大分数。

具体请看原题。

思路

根据“求最大值”这个问题，容易想到DP或者搜索。但是看一眼数据范围，搜索是不行了，DP的话，复杂度如果是O(N ^ 2)或者O(N ^ 2 * log N)都是可以接受的，所以考虑DP。

既然是DP，那么就需要确定dp数组的确切含义。

尝试一下常见的状态：dp[i]表示以 i 结束时可以得到的最大的分数。

ok，暂时就用这个状态。

观察一下题目，暂且认为tag全部不相同，从 i 到 j 需要满足 IQ < |ci - cj|，在这之后IQ = |ci - cj|，如果再往 k 走，需要满足IQ < |cj - ck|，也就是说要满足|ci - cj| < |cj - ck|，也就是说，如果把所有点连接起来，形成完全图，只能先走小权边，再走大权边。那么我们只需要把所有边全部存下来排序，再更新dp就可以了，但是我尝试了一下，内存会爆。

所以我们需要想一个不用存边但是可以按顺序遍历的方案。

因为这里的Ci = 2 ^ i，不难发现，任意两个点形成的边权值都是不同的，具体可以参考二进制的性质。假设a < b, c < d, Ca,b < Cc,d，那么一定有b < d，无论 a 和 c的大小关系。也就是说这个Ci只需要往后走一个点，就会增大一倍，前面所有的加起来都没有这个大。也可以这样理解：

Sum(C1, Ci) < C(i + 1)

这样我们就可以构造出一种边权从小到大遍历的方案了。具体看代码，复杂度O(T * N ^ 2)。

代码

/* Copyright (C) 2022 ErikTse */
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <utility>
#include <stack>
#include <algorithm>
#define pb push_back
#define fi first
#define se second
#define pr printf
#define sc scanf
#define gc getchar
#define int long long//注意使用%lld输出long long类型数据
using namespace std;
inline int readInt(){//快速读入int
	int s = 0,w = 1;char c = gc();
	while(c > '9' || c < '0')w = (c == '-' ? -1 : 1),c = gc();
	while('0' <= c && c <= '9')s = s * 10 + c - '0',c = gc();
	return s * w;
}
inline string readString(){//快速读入string
	string s;char c = gc();
	while(c == ' ' || c == '\n' || c == '\r')c = gc();
	while(c != ' ' && c != '\n' && c != '\r')s += c,c = gc();
	return s;
}
/*-------全局变量------*/
const int maxn = 5010;
int tag[maxn], s[maxn];//标签和分数 
int dp[maxn];//表示到 i 为止获得的分数最大值

/*-----自定义函数------*/
inline int getabs(int x){return x < 0 ? -x : x;}
inline void solve()
{
	int N = readInt();
	for(int i = 1;i <= N; ++ i)tag[i] = readInt();
	for(int i = 1;i <= N; ++ i)s[i] = readInt(), dp[i] = 0;
	//input finished
	for(int i = 1;i <= N; ++ i)
		for(int j = i - 1;j >= 1; -- j)
			if(tag[i] != tag[j])
			{
				int dpi = dp[i];//将dpi和dpj备份，防止后面出现数据失真 
				int dpj = dp[j];
				int val = getabs(s[i] - s[j]);
				dp[i] = max(dp[i], dpj + val);
				dp[j] = max(dp[j], dpi + val);
			}
	int ans = 0;
	for(int i = 1;i <= N; ++ i)ans = max(ans, dp[i]);
	pr("%lld\n",ans);
}

signed main()
{
	//freopen("in.txt","r",stdin);
	int T = readInt();
	while(T --)solve();
	return 0;
}