专栏文章

abc400_f 题解

bbeyoursven
AT_abc400_f题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipol2vc
此快照首次捕获于
2025/12/03 15:24
3 个月前
此快照最后确认于
2025/12/03 15:24
3 个月前
查看原文

题意

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

思路

根据数据范围，可以猜测使用区间 dp 求解。先考虑解决线性序列上的问题。
经过推导可以发现，两次染色的区间可以是不相交或者包含关系，但不可能是非包含但相交的关系。
定义 dpi,jdp_{i, j} 表示区间 [i,j][i, j] 染成目标颜色的最小代价。
对于不相交的情况，显然有：
dpi,j←min⁡i≤k<j{dpi,k+dpk+1,j}dp_{i, j} \gets \min \limits_{i \le k \lt j} \{ dp_{i, k} + dp_{k + 1, j} \}
对于包含情况，就是第一步把区间 [i,j][i, j] 染成颜色 CiC_i，再处理区间内部的染色，处理时，左端点 ii 的颜色不发生变化。
定义 gi,jg_{i, j} 表示区间 [i,j][i, j] 染成目标颜色而第一步先把区间 [i,j][i, j] 染成 CiC_i 的最小代价。该状态不能由 dpi,jdp_{i, j} 代替。
包含情况只可能出现在 Ci=CjC_i = C_j 时，有：
dpi,j←gi,jdp_{i, j} \gets g_{i, j}
考虑如何维护 gi,jg_{i, j}。
当区间 [i,j][i, j] 中至少两个目标颜色为 CiC_i 时，我们可以枚举 Ck=CiC_k = C_i 的位置 kk，将 gi,jg_{i, j} 的染色看做是 gi,kg_{i, k} 和 gk,jg_{k, j} 合并后的结果，此时有：
gi,j←min⁡i≤k<j,Ck+1=Ci{gi,k+gk+1,j−XCi}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][i, j] 染色为 CiC_i 后直接处理区间 [i+1,j][i + 1, j] 的染色，此时有：
gi,j←dpi+1,j+XCi+j−i+1g_{i, j} \gets dp_{i + 1, j} + X_{C_i} + j - i + 1

代码

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...