Omkar and Circle

2100的题一开始给我劝退了
擦

给一个长度为n的环，其中n为奇数，你可以选择一个数，把他替换成相邻两个数的和，再把相邻两个数删除，问执行多次操作之后，最后结果的最大值为多少？

也就是进行 n / 2 次操作，每次操作可以视为删除你选中的那个数。

因为操作的时候，选择的数字被替换为相邻两数的和，所以，本题可以理解为删除 n/2个不相邻的最小的数字。
问题来了！
如果两数合并替代中间数之后，会不会被当成最小的再次被替代？
不会！！！
因为选定值相邻两数过小的话，相邻的这两个数会被优先选定删除，剩下的中间的比较大，留着做贡献

不相邻的数，那么下标全为奇数或者偶数呗！

删除n/2个不相邻的，会剩下n/2+1个数，用总和减去删除的，即为答案
剩下n/2+1个数中，肯定会有两个数相邻

所以，首先对不相邻的全奇数或全偶数下标进行前缀和处理，之后枚举剩下的数中相邻两个数的位置
为什么？因为剩下两个数相邻，会导致前后的奇偶变化。

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 50;
int a[maxn];
long long dp[maxn][3];
//dp[i][0]表示i前面所有偶数的前缀和
//dp[i][1]表示i前面所有奇数的前缀和 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	long long sum = 0;//总和 
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
		sum += a[i];
		if(i == 1)
		{
			dp[i][1] = a[i];
			dp[i+1][1] = a[i];
		}
		else if(i == 2)
		{
			dp[i][0] = a[i];
			dp[i+1][0] = a[i];
		}
		else if(i % 2 == 1)
		{
			dp[i][1] = dp[i-2][1] + a[i];
			dp[i+1][1] = dp[i][1];
		}
		else
		{
			dp[i][0] = dp[i-2][0] + a[i];
			dp[i+1][0] = dp[i][0];
		}
	}
	long long ans = min(dp[n-2][1],dp[n-1][0]);
	//只是给ans定一个初值
	//dp[n-2][1]除去最后两个相邻的，（假设剩下的两个相邻的为最后）
	//dp[n-1][0]，所有偶数下标的和，（这时候，第一个与最后一个会被剩下，相邻）
	for(int i = 2; i <= n; i++)
	{
	//枚举剩下数字当中相邻两个的位置
		if(i % 2 == 0) ans = min(ans,dp[n][0] - dp[i-1][0] + dp[i-2][1]);
		//相邻的两个数占据 偶数，奇数下标，所以删除部分取较后的偶数与前面的奇数
		else ans = min(ans,dp[n][1] - dp[i-1][1] + dp[i-2][0]);
		//同理
	}
	if(n == 1) ans = 0;
	cout << sum - ans << endl;
	return 0;
}