1372 D. Omkar and Circle (思维、前缀和)

素颜马尾好姑娘i 2021-07-16 19:14 369阅读 0赞

[题目][Link 1]

思路：对于为n的奇数，可以进行(n-1)/2次让一个数取代相邻两数操作，直到最后只剩下一个数，其实每次操作就是删掉了一个数，那要如何让删除后的总和最大？ 首先贪心一下，我们一定不能删掉变成了两个数相加的那个数，如 1 2 3 4 5 假设第一步删掉1 -> 7 3 4 那之后删掉的数不能是7 因为 再删7=删掉1 2 5相当于删去了3个数，我们可以对比删掉2 5一定优于删掉1 2 5。而要不删掉已经加过一次的数就一定要删掉不是相邻的数，问题就转化成了从n个数中删掉(n-1)/2个不相邻的数（首尾也相邻），那么剩下的数中一定有两个是相邻的，我们枚举每两个相邻的数，预先统计奇偶前缀和即可。

如:1 2 3 4 5->  
（删1 3) 2 4 5  
（删1 4）2 3 5  
（删2 4）1 3 5  
（删2 5）1 3 4

Code:

#include<iostream>
    using namespace std;
    typedef long long ll;
    const int Max = 3e5 + 5;
    ll odd[Max], even[Max], lst[Max];
    
    int main()
    { 
    	int n;cin >> n;
    	for (int i = 1;i <= n;i++)
    	{ 
    		cin >> lst[i];
    		odd[i] = odd[i-1], even[i] = even[i - 1];
    		if (i & 1)odd[i] += lst[i];
    		else even[i] += lst[i];
    	}
    	ll ans = 0;
    	for (int i = 1;i <= n;i++)
    	{ 
    		if (i & 1)ans = max(odd[n] - odd[i - 1] + even[i], ans);
    		else ans = max(even[n] - even[i - 1] + odd[i], ans);
    	}
    	cout << ans << endl;
    }

[Link 1]: https://codeforc.es/contest/1372/problem/D

发表评论取消回复

表情：

评论列表（有 0 条评论，369人围观）

还没有评论，来说两句吧...

相关阅读

相关【前缀和优化DP】ABC 222D

虽然很简单，但是统一一下板子，以防写错 [D - Between Two Arrays (atcoder.jp)][D - Between Two Arrays _atcod

分手后的思念是犯贱/ 2024年03月17日 19:19/ 0 赞/ 75 阅读

相关 D. Non-zero Segments----前缀和

一维前缀和： sum\[0\] = 0; sum\[i\] = sum\[i-1\] + a

古城微笑少年丶/ 2022年11月19日 07:38/ 0 赞/ 138 阅读

相关 Codeforces Round #294 (Div. 2) D. A and B and Interesting Substrings [dp 前缀和 ]

[传送门][Link 1] D. A and B and Interesting Substrings time limit per test 2 seconds me

骑猪看日落/ 2021年12月23日 10:27/ 0 赞/ 176 阅读

相关 cf1173 D. Nauuo and Circle

链接 \[cf\][http://codeforces.com/contest/1175/problem/F][http_codeforces.com_contest_1

旧城等待，/ 2021年11月01日 10:18/ 0 赞/ 252 阅读

相关 D. Irreducible Anagrams (思维、前缀和、构造)

[题目][Link 1] 题意：一个字符串如果只是其中字符顺序被打乱则称其和原字符串相互为字谜。对于两个互为字谜的字符串，两个字符串按相同的位置分割开成为n(n>=2)个

偏执的太偏执、/ 2021年07月16日 22:40/ 0 赞/ 360 阅读

相关 1372 D. Omkar and Circle (思维、前缀和)

[题目][Link 1] 思路：对于为n的奇数，可以进行(n-1)/2次让一个数取代相邻两数操作，直到最后只剩下一个数，其实每次操作就是删掉了一个数，那要如何让删除后的总

素颜马尾好姑娘i/ 2021年07月16日 19:14/ 0 赞/ 370 阅读

相关 D. Divide and Sum (组合数、思维)

[添加链接描述][Link 1] 对于任意分组可以发现其实差值是一样的，将绝对值拆开，会发现都是后面n个大的-前面n的小的。看例子 a1 a2 a3 a4 a5

痛定思痛。/ 2021年07月16日 18:48/ 0 赞/ 339 阅读

相关 1455D Sequence and Swaps（思维）

D. Sequence and Swaps time limit per test 1.5 seconds memory limit per test

本是古典何须时尚/ 2021年07月16日 18:42/ 0 赞/ 319 阅读

相关 D. Divide and Summarize(思维)

[题目][Link 1] 思路：其实想一想不难看出我们只需要将所有的情况得到的值存储起来，然后在之后的问询阶段判断是否有这个值就可以了。然后注意一下当值都相同时进行特殊判

「爱情、让人受尽委屈。」/ 2021年07月16日 18:07/ 0 赞/ 371 阅读

相关 D. Tokitsukaze, CSL and Stone Game （思维、game）

[题目][Link 1] 思路：先手必输的情况： 1.有两个以上两堆石子数目相同。 2.有3堆以上石子数目相等、有两堆0石子。 3.有一个两堆数

今天药忘吃喽~/ 2021年07月16日 12:13/ 0 赞/ 366 阅读