题解：AT_abc400_f [ABC400F] Happy Birthday! 3

· · 题解

首先考虑序列。令 f(l,r) 表示将 [l, r] 改为目标状态的最小花费。

考虑 r 这个位置是如何变成目标状态的：

  1. 独自操作。即 f(l,r-1) + X_{C_r}+1 \longrightarrow f(l, r)。
  2. 考虑枚举 y \in [l, r-1] 且 C_y = C_r。当 y 这个位置变成目标状态时，我们考虑扩展这次操作的区间，使其右端点覆盖到 r。然后再操作 [y+1,r-1]。即 f(l,y)+r-y+f(y+1,r-1) \longrightarrow f(l, r)。因为是扩展，那么 X_{c_r} 的贡献就不用再算一次（已经在 f(l,y) 里算过了），将代价直接加上区间扩展的长度（r-y）即可。

然后考虑环。最直接的思路是倍长序列后做上面的区间 DP，然后求 f(i,i+n-1) 的最小值。可以证明破环为链是正确的，即一定存在两个相邻的位置，它们没有被同时操作过。枚举这个位置断开即可。

为什么？如果不存在这个位置，那么每次操作的区间的端点一定被操作过至少两次（除了这次还有另一次）。考虑最后一次操作的区间是 [l, r]，其中 r 端点还在 [l', r'] 这次操作中受到影响（r \in [l', r']），那么 [l',r'] 这次操作可以完全等价的改为 [l',r-1]（或 [r+1,r']）。那么这样就构造出了 r,r+1 这两个位置没有被同时操作过。

long long 是一定要开的。

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 810;

int n, c[N], x[N];
int f[N][N];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.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 <= n * 2; ++ i ) {
        f[i][i] = x[c[i]] + 1;
    }

    for (int len = 2; len <= 2 * n; ++ len )
        for (int l = 1, r = len; r <= 2 * n; ++ l, ++ r ) {
            f[l][r] = f[l][r - 1] + f[r][r];
            for (int x = l; x < r; ++ x )
                if (c[x] == c[r]) f[l][r] = min(f[l][r], f[l][x] + r - x + f[x + 1][r - 1]);
        }

    int res = 1e18;
    for (int l = 1, r = n; r <= 2 * n; ++ l, ++ r ) res = min(res, f[l][r]);
    cout << res;

    return 0;
}