Codeforeces 1497 D. Genius(DP + 可能有点图论)

发布于 2022-03-02  928 次阅读


原题传送门: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;
}
19岁,性别未知,ACM-XCPC退役选手,CCPC全国邀请赛金牌,ICPC亚洲区域赛银牌,武汉某院校计算机科学与技术专业本科在读。
最后更新于 2022-07-09