Haokee Note

CF1946B Maximum Sum

2 min read

贪心

题目大意

给定一个长度为 的数组 ，你需要进行 次操作，每一次操作都可以选择一个连续的子序列（可以为空），然后将这个子序列的和作为一个元素插入到这个数组当中。问你最后数组的和最大能够是多少，对 取模。

思路

首先，题目告诉了我们这题是「最大值取模」而不是「取模后的最大值」，因此我们可以考虑贪心。我们可以先找到最大字段和，然后把它的和插入到旁边这个操作等同于对最大字段和的值 ，而不会新加入其他的元素。因此，我们直接模拟就可以了。

代码

#include <iostream>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 2e5 + 5, kMod = 1e9 + 7;
 
LL a[kMaxN], dp[kMaxN], t, n, k, mx, ans;
 
int main() {
  for (cin >> t; t; t--) {
    cin >> n >> k, ans = mx = 0;
    for (LL i = 1; i <= n; i++) {
      cin >> a[i];
    }
    for (LL i = 1; i <= n; i++) {  // 求最大字段和
      mx = max(mx, dp[i] = max(dp[i - 1] + a[i], a[i]));
    }
    ans = -mx;  // 注意 ans 需要额外减去原来的部分
    for (; k--; mx = mx * 2 % kMod) { }  // 增长 n 次
    for (LL i = 1; i <= n; i++) {
      ans = (ans + a[i] + kMod) % kMod;  // 求数组和
    }
    cout << (ans + mx + kMod) % kMod << '\n';  // 加起来
  }
  return 0;
}

Graph View