GDKOI 2021 提高组 Day2 第三题 抄写（manachar+线段树维护DP）

GDKOI 2021 提高组 Day2 第三题 抄写

题目大意

• 要求按顺序写完一段小写字母组成的长为$n$的字符串，可以直接添加一个字符$i$，代价为$c_i$，也可以用当前末尾的部分轴对称，代价为$C$，求最小代价。
• $n\le 10^6$

题解

• 先考虑$n^2$的DP转移，$f_i=min(f_{i-1}+c_i,f_j+C)$，其中$j$是能作为对称轴的位置，可以用manachar预处理，$O(1)$判断合法的$j$。
• 观察到转移的贡献都是一样的$C$，那么可以直接从对称轴向后转移，用线段树用$log$的时间区间修改，避免了$O(n)$的转移。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 1000010
#define ll long long
ll f[N], g[N * 4];
int c[26], s0[N], s1[N];
char a[N];
void make(int v, int l, int r) {
	g[v] = 1e16;
	if(l == r) return ;
	int mid = (l + r) / 2;
	make(v * 2, l, mid), make(v * 2 + 1, mid + 1, r);
}
ll find(int v, int l, int r, int x) {
	if(l == r) return g[v];
	int mid = (l + r) / 2;
	g[v * 2] = min(g[v], g[v * 2]), g[v * 2 + 1] = min(g[v], g[v * 2 + 1]);
	if(x <= mid) return find(v * 2, l, mid, x);
	return find(v * 2 + 1, mid + 1, r, x);
}
void ins(int v, int l, int r, int x, int y, ll s) {
	if(l == x && r == y) {
		g[v] = min(g[v], s);
	}
	else {
		int mid = (l + r) / 2;
		g[v * 2] = min(g[v], g[v * 2]), g[v * 2 + 1] = min(g[v], g[v * 2 + 1]);
		if(y <= mid) ins(v * 2, l, mid, x, y, s);
		else if(x > mid) ins(v * 2 + 1, mid + 1, r, x, y, s);
		else ins(v * 2, l, mid, x, mid, s), ins(v * 2 + 1, mid + 1, r, mid + 1, y, s);
	}
}
int main() {
	int n, C, i, j;
	scanf("%d%d", &n, &C);
	for(i = 0; i < 26; i++) scanf("%d", &c[i]);
	scanf("
");
	scanf("%s", a + 1);
	int l = 1, r = 0, mid;
	for(i = 1; i <= n; i++) {
		s1[i] = 1, s0[i] = 0;
		if(l <= r && i <= r) {
			if((r - l + 1) % 2 == 0) {
				s0[i] = min(s0[2 * mid - i], r - i);
				s1[i] = min(s1[2 * mid - i + 1], r - i + 1);
			}
			else {
				s0[i] = min(s0[2 * mid - i - 1], r - i);
				s1[i] = min(s1[2 * mid - i], r - i + 1);
			}
		}
		while(i - s0[i] > 0 && i + s0[i] < n && a[i - s0[i]] == a[i + s0[i] + 1]) s0[i]++;
		while(i - s1[i] > 0 && i + s1[i] <= n && a[i - s1[i]] == a[i + s1[i]]) s1[i]++;
		if(i + s1[i] - 1 > r) l = i - s1[i] + 1, r = i + s1[i] - 1, mid = i;
		if(i + s0[i] > r) l = i - s0[i] + 1, r = i + s0[i], mid = i;
	} 
	f[0] = 0;
	make(1, 1, n);
	for(i = 1; i <= n; i++) {
		f[i] = find(1, 1, n, i);
		f[i] = min(f[i], f[i - 1] + (c[a[i] - 'a']));
		if(s1[i] > 1) ins(1, 1, n, i + 1, i + s1[i] - 1, f[i] + C);
		if(s0[i]) ins(1, 1, n, i + 1, i + s0[i], f[i] + C);
	}
	printf("%lld
", f[n]);
	return 0;
}

自我小结

• 考场上manachar维护最靠右的回文串写成了维护最长的回文串，挂了30分。忘记了的话可以想到右端点一定是单调向右移动的，这样才能保证$O(n)$的复杂度。

• 可见，复习算法很重要。