Codeforces Round #655 (Div. 2)（补题ing)

D. Omkar and Circle 【前缀和，区间DP思想】
题意： 在一个圆上排布着奇数个点，连续的3个点，可以合并为1个点，这个点的值由左右2个点的和决定【例如1 2 3可以合并成4,2的两侧1 + 3】，只要有3个以上的点，就可以不断进行合并，最后，圆上只会剩下一个点，要求这个点的值最大。
思路：明显的拆环成链区间DP。定义dp[i, j]为从i到j能得到的最大数值，注意区间长度为偶数的时候是无法合并成一个点的，所以dp的值为0.计算l->r的时候，选k为分界，i->k-1是一段，k+1->j是一段，合并这两段即可。【可以用来对拍qwq】

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

const int N = 1010;

int dp[N][N], w[N], n;

int main(){
    cin >> n;
    for(int i = 1; i <= n; ++ i)    cin >> w[i];
    for(int i = 1; i < n; ++ i)    w[i + n] = w[i];
    for(int len = 1; len <= 2 * n - 1; ++ len){
        for(int l = 1; l + len - 1 <= 2 * n - 1; ++ l){
            int r = l + len - 1;
            if(len == 1)    dp[l][r] = w[l];
            else if(len % 2 == 0)    dp[l][r] = 0;
            else{
                for(int k = l + 1; k < r; ++ k)
                    dp[l][r] = max(dp[l][r], dp[l][k - 1] + dp[k + 1][r]);
            }
        }
    }
    int ans = 0;
    for(int i = 1; i + n - 1 <= 2 * n - 1; ++ i){
        //printf("%d ", dp[i][i + n - 1]);
        ans = max(ans, dp[i][i + n - 1]);
    }
    cout << ans;
    return 0;
} 

but...n的范围是2e5,区间dp会tle+mle。所以借助区间dp的思想，画图发现，一定是间隔着选的
(1 0 1 0 1 0 1)。所以直接求一遍拆完的奇数前缀和和偶数前缀和，然后找最大值即可。

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

const int N = 200010;

ll odd[N], w[N * 2], even[N], n, oddcnt = 1, evencnt = 1, ans; 

int main(){
    cin >> n;
    for(int i = 1; i <= n; ++ i)    cin >> w[i];
    for(int i = 1; i < n; ++ i)    w[i + n] = w[i];
    for(int i = 1; i <= 2 * n - 1; i += 2)    odd[oddcnt] = odd[oddcnt - 1] + w[i], oddcnt ++;        //奇数前缀和
    for(int i = 2; i <= 2 * n - 1; i += 2)    even[evencnt] = even[evencnt - 1] + w[i], evencnt ++;    //偶数前缀和
    int num = n / 2 + 1;
    for(int i = 1; i + num - 1 < oddcnt; ++ i){
        ans = max(ans, odd[i + num - 1] - odd[i - 1]);
        //cout << odd[i + num - 1] - odd[i - 1] << endl;
    }        
    for(int i = 1; i + num - 1 < evencnt; ++ i)        ans = max(ans, even[i + num - 1] - even[i - 1]);
    cout << ans;
    return 0;
} 

tips:有题解说只需要看奇数的前缀和emm..感觉毫无道理，比如5
1 7 3 9 0 （1 7 3 9） 最大值是17（7 + 9 + 1）而不是16.可能是写法不同？