邮寄

开场半个小时秒了 B。

然后看 A，钻研了一个多小时吧，过了。

然后看 CD。结果 D 是大模拟，还是有文化的大模拟，直接使我停机，卡完了剩下两个小时，然后没分。

我爸让我沉下心来想一想，这就是后果，score-60

总共 200。

A 变幻

易得连续两个数不会一起操作。

所以就可以设 \(dp_{i, j}\) 表示考虑前 \(i\) 个，操作了 \(j\) 次的最大权值。

由于最后一个数不会被操作，转移易得：

当 \(a_{i + 1}\) 是山谷数时，\((i, j) \to (i + 2, j) + a_{i + 1}\)

否则：\((i, j) \to (i + 1, j), (i, j) \to (i + 2, j + 1) + (\min(a_i, a_{i + 2}) – 1)\)

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, k, arr[2020], dp[2020][2020];

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

B 交替

结论题。

记 \(l = \lceil \frac{n}{2} \rceil – 1\)。

当 \(n\) 是奇数，答案为 \(\sum \limits_{i = 0}^l (-1)^i \binom{l}{i} a_{2i}\)；

否则，答案为 \(\sum \limits_{i = 0}^l (-1)^i \binom{l}{i} (a_{2i} + a_{2i + 1})\)

处理一下组合数直接算就行了。至于这个规律咋来的，我是手玩了 \(n\) 比较小的情况。

#include <bits/stdc++.h>
#define int ll
using namespace std;
using ll = long long;

const int kMod = int(1e9) + 7;

int n, arr[100010], fac[100010], inv[100010], rl, ans, val;

int qinv(int x) {
  int rs = 1;
  for(int tmp = kMod - 2; tmp; tmp >>= 1) {
    if(tmp & 1) {
      rs = 1ll * rs * x % kMod;
    }
    x = 1ll * x * x % kMod;
  }
  return rs;
}

void init() {
  fac[0] = 1;
  for(int i = 1; i <= 100000; i++) {
    fac[i] = 1ll * fac[i - 1] * i % kMod;
  }
  inv[100000] = qinv(fac[100000]);
  for(int i = 99999; i >= 0; i--) {
    inv[i] = 1ll * inv[i + 1] * (i + 1) % kMod;
  }
}

long long c(int x, int y) {
  if(x < 0 || y < 0 || x < y) {
    return 0;
  }
  return 1ll * fac[x] * inv[x - y] % kMod * inv[y] % kMod;
}

signed main() {
  freopen("alternate.in", "r", stdin);
  freopen("alternate.out", "w", stdout);
  init();
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  rl = (n + 1) / 2 - 1, val = 1;
  if(n & 1) {
    for(int i = 0; i <= rl; i++) {
      ans = (ans + val * c(rl, i) * arr[i << 1] % kMod + kMod) % kMod;
      val = val * -1;
    }
  }else {
    for(int i = 0; i <= rl; i++) {
      ans = (ans + val * c(rl, i) * (arr[i << 1] + arr[(i << 1) | 1]) % kMod + kMod) % kMod;
      val = val * -1;
    }
  }
  cout << ans << '\n';
  return 0;
}

/*
auto [x, y, z] = ...
*/