2024/09/25 模拟赛总结

rk5，\(100+40+5+0=145\)。T2 上物理课把式子推出来了，感谢孟德的馈赠

#A. 变换

简单 dp，为什么都写 \(3\) 维啊

令 \(dp_{i,j,0/1,0/1}\) 为考虑前 \(i\) 位改了 \(j\) 位，当前是/不是“山谷”，前一位是/不是“山谷”

显然，相邻两位一定不会都是山谷，所以 \(dp_{i,j,1,1}\) 一定不存在

考虑转移。对于 \(dp_{i,j,0,0}\)，只要上一位不是“山谷”即可，即 \(dp_{i,j,0,0}=\max\{dp_{i-1,j,0,0},dp_{i-1,j,0,1}\}\)

对于 \(dp_{i,j,0,1}\)，上一位的上一位一定不为“山谷”，所以 \(dp_{i,j,0,1}=dp_{i-1,j,1,0}\)

对于 \(dp_{i,j,1,0}\)，需要分类讨论。若第 \(i\) 本来就是“山谷”，则 \(dp_{i,j,1,0}=a_i+\max\{dp_{i-1,j,0,0},dp_{i-1,j,0,1}\}\)；否则 \(dp_{i,j,1,0}=\min\{a_{i-1},a_{i+1}\}-1+\max\{dp_{i-1,j-1,0,0},dp_{i-1,j-1,0,1}\}\)

最终答案为 \(\max\{dp_{n,i,0,0/1}\}\)

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 2e3 + 5;

int n, k, tot;
LL ans, a[kMaxN], f[kMaxN][kMaxN][2][2];

int main() {
  freopen("change.in", "r", stdin), freopen("change.out", "w", stdout);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 2; i < n; i++) {
    if (a[i] < a[i + 1] && a[i] < a[i - 1]) {
      for (int j = 0; j <= min(i, k); j++) {
        f[i][j][1][0] = max({f[i - 1][j][0][0], f[i - 1][j][0][1]}) + a[i];
        f[i][j][0][1] = f[i - 1][j][1][0];
        f[i][j][0][0] = max({f[i - 1][j][0][0], f[i - 1][j][0][1]});
      }
    } else {
      for (int j = 0; j <= min(i, k); j++) {
        f[i][j][0][0] = max({f[i - 1][j][0][0], f[i - 1][j][0][1]});
        f[i][j][0][1] = f[i - 1][j][1][0];
        j && (f[i][j][1][0] = max({f[i - 1][j - 1][0][1], f[i - 1][j - 1][0][0]}) + min(a[i - 1], a[i + 1]) - 1);
      }
    }
  }
  for (int j = 0; j <= k; j++) {
    f[n][j][0][0] = max({f[n - 1][j][0][0], f[n - 1][j][0][1]});
    f[n][j][0][1] = max({f[n - 1][j][1][0], f[n - 1][j][1][0]});
  }
  for (int i = 0; i <= k; i++) {
    ans = max({ans, f[n][i][0][0], f[n][i][0][1]});
  }
  cout << ans << '\n';
  return 0;
}