文章目录[x]
- 1:题目链接
- 2:题面
- 3:题意
- 4:思路
- 5:参考代码
题目链接
https://codeforces.com/contest/1372/problem/D
题面
题意
给定个数字,组成一个环,每次你可以取相邻的两个数去替换这个数,收益为这个和,问合并到最后的最大值为多少。
思路
显然,个数,要合并次,那么问题就转化为了,个数找个数而且只有一对数相邻的最大值,那么枚举这对相邻的数即可,前缀处理一下:
记录到为止下标为偶数的前缀和
记录到为止下标为奇数的前缀和
然后枚举求最大值即可。
参考代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
LL dp[N][2], a[N], n;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[n + i] = a[i];
}
for (int i = 1; i <= 2 * n; i++) {
dp[i][0] = dp[i - 1][0];
dp[i][1] = dp[i - 1][1];
dp[i][(i + 1) % 2] += a[i - 1];
}
LL ans = 0;
for (int i = 1; i <= n; i++) {
ans = max(ans, a[i] + dp[i + n][i % 2] - dp[i + 1][i % 2]);
}
cout << ans << endl;
return 0;
}