D. Omkar and Circle(非常有意思的一道题)
Problem - D - Codeforces
丹尼是当地的数学狂人，他对圆形很着迷，这是奥姆卡最近的发明。帮他解决这个圆的问题!已知n个非负整数a1, a2，， an，它们排成一个圆，其中n必须是奇数。n -1能被2整除)。形式上，对于所有的é，使得2si≤n，元素a-1和a被认为是相邻的，an和a1也被认为是相邻的。在一个操作中，您在圆上选择一个数字，将其替换为与之相邻的两个元素的和，然后从圆中删除这两个相邻元素。如此重复，直到圆圈中只剩下一个数字，我们称之为循环值。帮助Danny在一些操作序列后找到可能的最大循环值。输入第一行包含一个奇数n (1 <n <2-105, n是奇数)-圆的初始大小。第二行包含n个整数a1, a2，..， an(0≤ai < 10°)-圆中的初始数。输出在对给定的圆应用一些操作序列后，输出可能的最大循环值。
Examples
input
Copy
3 7 10 2
output
Copy
17
input
Copy
1 4
output
Copy
4
请注意对于第一个测试用例，下面是如何获得循环值17:取下标3处的数。相邻元素的和等于17。从圆中删除7和10，用17代替2。注意，答案可能不适合32位整数。
题解:
每次选一个数,删去旁边两个不相邻的数,并且让这个数等于两个被删除数的和,其实就是所有不相邻数和的最大值
写题的时候可能会想到这一点,但是
举个例子
1 2 3 4 = [1,3]
2 3 4 1 = [2,4]
3 4 1 2 = [3,1]
4 1 2 3 = [4,2]
对于偶数环,很容易想到,不同的情况只有两种,稍微不细想的话,我们可能会觉得奇数环偶数环一样(毕竟是环),
但是,其实是不一样
所以,我们先把数组扩充为2*n,利用前缀和求最大即可
(我们在写题时,很容易犯一些我感觉是对的错误(基于经验或感觉曾经见过这样的题,导致没有想而出现错误))
盲目的自信比愚蠢更可怕
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#define int long long
int a[400050];
void solve()
{int n;cin >> n;for(int i = 1;i <= n;i++){cin >> a[i];a[n + i] = a[i];}for(int i = 2;i <= 2*n;i++){a[i] = a[i - 2] + a[i];} int ans = 0;for(int i = n + 1;i <= 2*n;i++){ans = max(ans,a[i] - a[i - n - 1]);}cout << ans;
}signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);int t = 1;
// cin >> t;while(t--){solve(); }
}