[前缀和dp] CF1372D. Omkar and Circle

题目

n个数字组成一个环，每次选择一个数字将其相邻的两个值赋给他，然后删除相邻的值，这样操作只剩一个值，求这个值的最大值。

思路

一共有n个数，且n为奇数，即一共删除n/2个数，留下n/2+1个数且删除的数皆不相邻。
即求删除的数的和的最小值。
由于有n/2+1个数不被删除，一定有两个不被删除的数是相邻的，我们就枚举这两个数的位置。
设相邻两个数的后一个数下标为i
dp[i][0]为i前下标为偶数的前缀和
dp[i][1]为i前下表为奇数的前缀和

数列	转移方程
1 2 3 4 5 6 7	dp[n-2][1]
1 2 3 4 5 6 7	dp[n-1][0]
1 2 3 4 5 6 7	dp[n][0]-dp[i-1][0]+dp[i-2][1]
1 2 3 4 5 6 7	dp[n][1]-dp[i-1][1]+dp[i-2][0]

代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<ctime>
#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<iomanip>
#include<list>
#include<bitset>
#include<sstream>
#include<fstream>
#include<complex>
#include<algorithm>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ll long long
#define int long long
using namespace std;
const int INF = 0x3f3f3f3f;
int dp[200010][3];
int a[200010];
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	int res=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		res+=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];
		}
	}
	int ans=min(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<<res-ans<<endl;
    return 0;
}

本文地址：https://blog.csdn.net/kosf_/article/details/107299251