D. Omkar and Circle 【前缀和，区间DP思想】

```#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.可能是写法不同？