原题传送门: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; }
Comments NOTHING