-
题意
-
给你一个长度为 n 的数组(保证 n 为奇数)，数组头尾相连变成一个环。现在你需要对这个环进行多次如下操作直到数组中只剩下一个数，使得最后这个数最大。
-
操作方法：选择数组中的一个数，将其替换为相邻左右两数的合，并且删除掉左右两边的数。
也就是说跟原数组相比，x 位置上的数变成 (x-1) 和 (x+1) 位置上的数的和(这里要注意数组首尾相连是一个环状的)，而 (x-1) 和 (x+1) 位置上的数则删去，每次操作删除两个数，因为保证 n 为奇数，所以总共的操作共 ((n-1)/2) 次。
-
-
解析
- 刚开始很容易想到，最后得到的这个数，是由数组中的 ((n-1)/2 + 1) (令为 m )个数的和组成的，但又不是任意 m 个数所组合出的数一定能行，在自己的思考过程中会发现，如果考虑对 n 个数中进行题目要求的操作方法，得到的和是由 m 个数组成，这 m 个数有的相邻而有的不相邻，不是很好考虑。
- 那我们就要另辟蹊径，选择找出被替换的数，我们知道操作数为 ((n-1)/2) (令为 k ) 次，所以就替换了 k 个数，也就是说这 k 个数没有对答案有贡献，所以答案就是 (Sum - k个数的和)。因为在操作的时候，会删除掉被替换位置两边的数，所以被替换的数是一定没有相邻的。那么我们只要找到所有可能的 k 个数的和，选择其最小的即可得到答案。
- 那么如何找到所有的 k 个数的和呢？实际上就是 1~n 从其中每一个位置为起点，隔一个数取一个数，共取 ((n-1)/2) 次。
- 例如：当 n = 5 时，有 5 种取法，分别是 (1,3),(2,4),(3,5),(4,1),(5,2)。
- 如果 n = 5 还不能理解，试着想想 n = 7 的情况，如果刚开始取走了 1 和 3，那么我下一步可以取走 5 或 6，那可能会问，取走 6 这时不就不是隔一个数取一个数，这时如果理解为从 6 开始，那就是 (6,1,3)，依旧是隔一个数取一个数。
- 现在我们已经找到了所有可能的 k 个数的构成，那么要如何高效的得到和呢，现在我们将原数组倍长，并预处理好奇数位置上和偶数位置上的前缀和，之后就是计算 (Min(sum[i+n-2]-sum[i-1]))。
-
最后上代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Maxn = 2e5+10;
const int Inf = 0x7f7f7f7f;
int a[Maxn<<1];
ll Sum[Maxn<<1],tol;
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),a[i+n] = a[i],tol += a[i];
Sum[1] = a[1];
for(int i=2;i<=2*n;i++)
Sum[i] = Sum[i-2] + a[i];
ll Min = 1ll*Inf*Inf;
for(int i=1;i<=n;i++)
{
ll tmp = Sum[i+n-2] - Sum[i-1];
Min = min(Min,tmp);
}
printf("%lld
",tol-Min);
return 0;
}