专栏文章

题解：AT_abc400_f [ABC400F] Happy Birthday! 3

22huk
AT_abc400_f题解参与者 5已保存评论 4

文章操作

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

当前评论
4 条
当前快照
1 份
快照标识符
@mippfxc0
此快照首次捕获于
2025/12/03 15:48
3 个月前
此快照最后确认于
2025/12/03 15:48
3 个月前
查看原文
首先考虑序列。令 f(l,r)f(l,r) 表示将 [l,r][l, r] 改为目标状态的最小花费。
考虑 rr 这个位置是如何变成目标状态的：
  1. 独自操作。即 f(l,r−1)+XCr+1⟶f(l,r)f(l,r-1) + X_{C_r}+1 \longrightarrow f(l, r)。
  2. 考虑枚举 y∈[l,r−1]y \in [l, r-1] 且 Cy=CrC_y = C_r。当 yy 这个位置变成目标状态时，我们考虑扩展这次操作的区间，使其右端点覆盖到 rr。然后再操作 [y+1,r−1][y+1,r-1]。即 f(l,y)+r−y+f(y+1,r−1)⟶f(l,r)f(l,y)+r-y+f(y+1,r-1) \longrightarrow f(l, r)。因为是扩展，那么 XcrX_{c_r} 的贡献就不用再算一次（已经在 f(l,y)f(l,y) 里算过了），将代价直接加上区间扩展的长度（r−yr-y）即可。
然后考虑环。最直接的思路是倍长序列后做上面的区间 DP，然后求 f(i,i+n−1)f(i,i+n-1) 的最小值。可以证明破环为链是正确的，即一定存在两个相邻的位置，它们没有被同时操作过。枚举这个位置断开即可。
为什么？如果不存在这个位置，那么每次操作的区间的端点一定被操作过至少两次（除了这次还有另一次）。考虑最后一次操作的区间是 [l,r][l, r]，其中 rr 端点还在 [l′,r′][l', r'] 这次操作中受到影响（r∈[l′,r′]r \in [l', r']），那么 [l′,r′][l',r'] 这次操作可以完全等价的改为 [l′,r−1][l',r-1]（或 [r+1,r′][r+1,r']）。那么这样就构造出了 r,r+1r,r+1 这两个位置没有被同时操作过。
long long 是一定要开的。
CPP
#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;
}

评论

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

正在加载评论...