Codeforces Round #655 (Div. 2) D

文章目录[x]
  1. 1:题目链接
  2. 2:题面
  3. 3:题意
  4. 4:思路
  5. 5:参考代码




D

题目链接

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;
}


点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像