QOJ #10485. Peculiar Protocol 题解

Description

你有一个序列 $a_1, a_2, \dots, a_n$，以及两个参数 $d, r$。

你可以做如下操作若干次：

• 每次选择一段区间，使得他们的和可以被表示成 $k \times d + r$ 的形式，其中 $k$ 是一个非负整数。
• 你把 $k$ 加入分数中，然后在序列中删去这一段，剩下的序列合在一起。

比如说 $d=5, r=1$，序列为 $2, 2, 2, 4, 4$。

• 那么你可以删除 $2, 2, 2$，获得 $1$ 的分数。序列无法继续进行操作。
• 你也可以删除 $2, 4$，获得 $1$ 的分数，序列变为 $2, 2, 4$。你可以继续删除 $2, 4$，一共获得 $2$ 的分数。

问最多可以获得多少分数。

$n\leq 500,a_i,d,r\leq 10^8$。

Solution

首先这题显然是区间 dp。

有个想法是设 $f_{l,r}$ 表示把 $[l,r]$ 删空的最小次数，转移时要枚举在最后一次操作之前删空了 $[l,r]$ 内的哪些子区间。

由于知道了操作次数就能知道剩余数模 $d$ 的值，所以加一个状态 $g_{l,r,k}$ 表示当前 $[l,r]$ 做了 $k$ 次操作是否可行，暴力转移是 $O(n^4)$。

注意到 $g_{l,r,k}$ 中的 $k$ 毫无意义，因为能够操作出来的操作次数一定是一段前缀，所以将状态改为 $g_{l,r}$ 表示 $[l,r]$ 的最多操作次数即可，转移可以暴力转移。

时间复杂度：$O(n^3)$。

Code

#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 505;

int n, d, r;
int a[kMaxN], f[kMaxN][kMaxN];
int64_t s[kMaxN], g[kMaxN][kMaxN];

void dickdreamer() {
  std::cin >> n >> d >> r;
  for (int i = 1; i <= n; ++i) {
    std::cin >> a[i];
    s[i] = s[i - 1] + a[i];
  }
  memset(f, 0, sizeof(f));
  memset(g, 0, sizeof(g));
  for (int len = 1; len <= n; ++len) {
    for (int i = 1; i <= n - len + 1; ++i) {
      int j = i + len - 1, sum = s[j] - s[i - 1];
      for (int k = i; k < j; ++k) f[i][j] = std::max(f[i][j], f[i][k] + f[k + 1][j]);
      if ((sum - r * f[i][j] % d + d) % d == r) ++f[i][j];
      for (int k = 1; k <= f[i][j]; ++k) {
        if (k * r % d == sum % d) {
          g[i][j] = (sum - k * r) / d;
          break;
        }
      }
      // std::cerr << i << ' ' << j << ' ' << f[i][j] << ' ' << g[i][j] << '\n';
    }
  }
  // std::cerr << "??? " << f[3][4] << ' ' << f[2][5] << '\n';
  for (int i = n; i; --i) {
    for (int j = i; j <= n; ++j)
      for (int k = i; k < j; ++k)
        g[i][j] = std::max(g[i][j], g[i][k] + g[k + 1][j]);
  }
  std::cout << g[1][n] << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}