abc400_f 题解

· · 题解

题意

给定一个大小为 N 的环形序列，序列中每个元素初始时无色。每次操作中，可以选择序列中一个长度为 M（M \le N）的连续子序列染成颜色 c，代价为 X_c + M。现在序列中每个元素需要染成目标颜色 C_i，求最小总代价。

思路

根据数据范围，可以猜测使用区间 dp 求解。先考虑解决线性序列上的问题。

经过推导可以发现，两次染色的区间可以是不相交或者包含关系，但不可能是非包含但相交的关系。

定义 dp_{i, j} 表示区间 [i, j] 染成目标颜色的最小代价。

对于不相交的情况，显然有：

dp_{i, j} \gets \min \limits_{i \le k \lt j} \{ dp_{i, k} + dp_{k + 1, j} \}

对于包含情况，就是第一步把区间 [i, j] 染成颜色 C_i，再处理区间内部的染色，处理时，左端点 i 的颜色不发生变化。

定义 g_{i, j} 表示区间 [i, j] 染成目标颜色而第一步先把区间 [i, j] 染成 C_i 的最小代价。该状态不能由 dp_{i, j} 代替。

包含情况只可能出现在 C_i = C_j 时，有：

dp_{i, j} \gets g_{i, j}

考虑如何维护 g_{i, j}。

当区间 [i, j] 中至少两个目标颜色为 C_i 时，我们可以枚举 C_k = C_i 的位置 k，将 g_{i, j} 的染色看做是 g_{i, k} 和 g_{k, j} 合并后的结果，此时有：

g_{i, j} \gets \min \limits_{i \le k \lt j, C_{k + 1} = C_i} \{ g_{i, k} + g_{k + 1, j} - X_{C_i}\}

我们还可以考虑当区间 [i, j] 染色为 C_i 后直接处理区间 [i + 1, j] 的染色，此时有：

g_{i, j} \gets dp_{i + 1, j} + X_{C_i} + j - i + 1

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 4e2 + 1;
const ll INF = 1e18;

int n, c[2 * MAXN], x[MAXN];
ll ans = LLONG_MAX, dp[2 * MAXN][2 * MAXN], g[2 * MAXN][2 * MAXN];

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> c[i];
    c[i + n] = c[i];
  }
  for (int i = 1; i <= n; i++) {
    cin >> x[i];
  }
  for (int i = 1; i <= 2 * n; i++) {
    dp[i][i] = g[i][i] = x[c[i]] + 1;
  }
  for (int len = 2; len <= n; len++) {
    for (int i = 1, j = i + len - 1; j <= 2 * n; i++, j++) {
      dp[i][j] = INF, g[i][j] = x[c[i]] + j - i + 1 + dp[i + 1][j];
      for (int k = i; k < j; k++) {
        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
        if (c[i] == c[k + 1]) {
          g[i][j] = min(g[i][j], g[i][k] + g[k + 1][j] - x[c[i]]);
        }
      }
      if (c[i] == c[j]) {
        dp[i][j] = min(dp[i][j], g[i][j]);
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    ans = min(ans, dp[i][i + n - 1]);
  }
  cout << ans;
  return 0;
}