[CF1372D] Omkar and Circle

Description

给定一个长度为奇数 (n) 的环形序列，进行若干次操作：选择 (i)，将其替换为 (a_{i-1}+a_{i+1})，并删除 (a_{i-1},a_{i+1})。最后剩下一个数。求最后剩下的数的最大值。

Solution

找规律发现，会对答案产生贡献的，一定是第 (...,i-4,i-2,i,i+1,i+3,i+5,...) 个数的和。

暴力枚举 (i)，前面只取奇偶性与 (i) 相同的，后面只取奇偶性与 (i) 不同的，最后取最大值即可。

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 1000005;

int n,a[N],s[N][2],ans;

signed main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) s[i][0]=s[i-1][0], s[i][1]=s[i-1][1], s[i][i&1]+=a[i];
    for(int i=1;i<=n;i++) ans=max(ans, s[i][i&1]+s[n][(i&1)^1]-s[i][(i&1)^1]);
    cout<<ans<<endl;
}