原题传送门：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;
}
文章评论