【每日一题】数学考试

Statement

今天qwb要参加一个数学考试，这套试卷一共有道题，每道题qwb能获得的分数为，qwb并不打算把这些题全做完，他想选总共道题来做，并且期望他能获得的分数尽可能的大，他准备选个不连续的长度为的区间，即。
其中有。

Solution

把题意简单点说：将一个数组分成两个长度均为且不相交的子串，使得这两个子串的和最大。

那么令表示第个位置前面选了个这样的区间所能得到的最大值，那么就容易得到转移式：

当且时

上面的求和式子可以用前缀和优化成。

其余情况则有

于是答案就是，而不是是因为这两个区间是一定要取的而不是想取到个。即全体负数的情况下也要选两个负数区间最小的。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void Main();
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie();
  Main();
  return 0;
}

void Main() {
  int T; cin >> T;
  while(T--) {
    int n, k; cin >> n >> k;
    vector<int> a(n + 1, 0); // 获得分数
    vector<ll> pre(n + 1, 0); // 前缀和
    vector<vector<ll>> dp(n + 1, vector<ll>(3, -1e13)); // 动态规划数组
    for(int i = 1; i <= n; i++) {
      cin >> a[i];
      pre[i] = pre[i - 1] + a[i]; // 求前缀和
    }
    dp[0][0] = 0;
    for(int i = 1; i <= n; i++) {
      for(int j = 0; j < 3; j++) {
        dp[i][j] = dp[i - 1][j]; // 不以第i个数为结尾的区间能取到的最大值
      }
      if(i >= k) {
        // 与以第i个数为结尾的区间作为第一个区间能取到的最大值
        dp[i][1] = max(dp[i][1], dp[i - k][0] + pre[i] - pre[i - k]);
        // 与以第i个数为结尾的区间作为第二个区间能取到的最大值
        dp[i][2] = max(dp[i][2], dp[i - k][1] + pre[i] - pre[i - k]);
      }
    }
    cout << dp[n][2] << '\n';
  }
}