ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

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

2022年3月2日 778点热度 0人点赞 0条评论

原题传送门: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: codeforces DP 动态规划 图论 思维
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目大意
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号