文档章节

[codeforces 1372D] Omkar and Circle 圆上区间动归

o
 osc_9mt0ncuk
发布于 07/14 13:28
字数 626
阅读 102
收藏 0
c++

行业解决方案、产品招募中!想赚钱就来传!>>>

Codeforces Round #655 (Div. 2)   参与排名人数15842   天天熬夜打比赛,身体吃不消,作了一个充满幸福感的决定,赛后第二天再刷

[codeforces 1372D]   Omkar and Circle   圆上区间动归

总目录详见https://blog.csdn.net/mrcrack/article/details/103564004

在线测评地址http://codeforces.com/contest/1372/problem/D

Problem Lang Verdict Time Memory
D - Omkar and Circle GNU C++17 Accepted 93 ms 7000 KB

题目大意:在一个圆上排布着奇数个点,连续的3个点,可以合并为中间这个点,这个点的值由左右2个点的和值决定,只要有3个以上的点,就可以不断进行合并,最后,圆上只会剩下一个点,要求这个点的值最大。

基本思路:题目看完,意识到是区间动归,但看了数据范围1≤n<2⋅10^5,区间动归明显吃不消,区间动归承受的范围通常是n<=1000。用一下区间动归思路进行研究。

区间动归研究状态较多,里面存在较多无用状态。如下数据为例

研究a[1],a[2],a[3],a[4],a[5],a[6],a[7].

a[1]一定要参与最左数据的计算,a[7]一定要参与最右数据的计算。
按区间动归的思路,存在如下状态。

(a[1],a[2],a[3]),a[4],(a[5],a[6],a[7])
对应最终结果a[1]+a[3]+a[5]+a[7]

(a[1],a[2],a[3]),(a[4],a[5],a[6]),a[7]
对应最终结果a[1]+a[3]+a[7]

(((a[1],a[2],a[3]),a[4],a[5]),a[6],a[7])
对应最终结果a[1]+a[3]+a[5]+a[7]

a[1],(a[2],a[3],a[4]),(a[5],a[6],a[7])
对应最终结果a[1]+a[5]+a[7]

((a[1],a[2],(a[3],a[4],a[5])),a[6],a[7])
对应最终结果a[1]+a[3]+a[5]+a[7]

......

根据一系列的状态,可以很明显的看出,最大值是一个连续脚标差值为2的序列a[1]+a[3]+a[5]+a[7],
该种序列,无需再进行区间动归,直接找脚标差值为2的序列。

AC代码如下:

#include <cstdio>
#include <algorithm>
#define maxn 200010
#define LL long long
using namespace std;
LL a[maxn<<1],ans;
int main(){
	int n,i;
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%lld",&a[i]),a[i+n]=a[i];//化圆为线
	for(i=3;i<=2*n;i++)a[i]+=a[i-2];
	for(i=n+1;i<=2*n;i++)ans=max(ans,a[i]-a[i-n-1]);
	printf("%lld\n",ans);
	return 0;
}

 

o
粉丝 0
博文 72
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
工作流管理系统--Pegasus WMS

Pegasus (飞马座)工作流管理系统包括一套技术标准工作流程应用程序中执行帮助许多不同的环境中,包括桌面、校园集群、网格、云。它弥补了科学领域和执行环境通过自 动映射到分布式资源的高层工...

匿名
2013/02/24
5.3K
0
实践 HTML5 的 CSS3 Media Queries

先来介绍下 media,确切的说应该是 CSS media queries(CSS 媒体查询),媒体查询包含了一个媒体类型和至少一个使用如宽度、高度和颜色等媒体属性来限制样式表范围的表达式。CSS3 加入的媒体...

xhload3d
2016/06/21
383
0
Android动画:一个等待动画的制作过程

看到一个很好玩的gif等待动画,记录一下制作过程。 先上图,展示一下这gif。 图中四个空心圆,一个实心园,依次作规则双星运动。 三个晚上,目前已经已经实现了。又学到了不少东西,这几天把...

宋昊
2016/06/03
931
0
搞定编程大赛必知哪10个算法?

再没有比算法更让人头疼的东西了吧! 前两天参加了一个编程大赛http://www.ijiami.cn/newsInfo?id=519&v=2,有感于算法,所以整理了这篇关于编程竞赛的10个算法。 动态规划(DP)似乎占据了大...

小开2014
2014/10/22
396
6
[转载]在iTOP-4412开发板上调试helloworld应用

本文转自迅为论坛:http://www.topeetboard.com 1.安装ADB驱动 在开发板上调试 Android 应用,首先要安装 ADB 驱动。 通过“SDK Manager.exe”来安装。如下图所示。另外需要注意的是,如果要...

歌之王子殿下
2015/12/17
271
0

没有更多内容

加载失败,请刷新页面

加载更多

重拾Java反射(为什么?)

前言:如标题所述,为什么要重拾Java反射?究其缘由,在Java中反射具有举足轻重的地位,一直以来都是Java中的闪亮点,并且反射是一系列出众的web框架设计的灵魂所在。PS:本文主要是理论,篇...

Umizhang
2019/06/07
0
0
删除文本文件中包含特定字符串的行 - Delete lines in a text file that contain a specific string

问题: 我将如何使用sed删除文本文件中包含特定字符串的所有行? 解决方案: 参考一: https://stackoom.com/question/MhaH/删除文本文件中包含特定字符串的行 参考二: https://oldbug.net...

富含淀粉
1分钟前
0
0
巧用 Matplotlib 动画,让你的 Python 可视化大放异彩

— 1 — 前言 如果你对本文的代码感兴趣,可以去 Github (文末提供)里查看。第一次运行的时候会报一个错误(还没找到解决办法),不过只要再运行一次就正常了。 这篇文章虽然不是篇典型的数...

Python大数据分析
05/19
0
0
如何追班花?贝叶斯公式来帮忙

0 1 条件概率 在某个美丽的校园里,小扎喜欢上了班花小美,暗恋了很久终于想鼓起勇气追小美。 但是小扎知道自己长得不帅,不是富二代,成绩也不是很好,追小美这件事,小扎在心里估算了下,成...

zhanyd
01/12
0
0
Docker中级篇|深入探究Docker

简介: 深入探究Docker Docker镜像理解 Docker镜像是什么 镜像是一种轻量级、可执行的独立软件包,用来打包软件运行环境和基于运行环境开发的软件,它包含运行某个软件所需的所有内容,包括代...

一肥仔
2分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部