题目大意
给定四种对字符串$S$的操作：
push_back(P)：在$S$后连接一个字符串$P$，即$S\leftarrow S+P$，代价为$\left|P\right|$。push_back(P)：在$S$前连接一个字符串$P$，即$S\leftarrow P+S$，代价为$\left|P\right|$。symmetry_back()：将$S$翻转后连接到$S$之后，即$S\leftarrow S+S^T$，代价为$1$。symmetry_front()：将$S$翻转后连接到$S$之前，即$S\leftarrow S^T+S$，代价为$1$。给定一个目标串$S$，要求你通过上述四种操作，用最少的代价合成出目标串。初始只有一个空串。
题目分析
本题可以通过Hash寻找回文串，然后使用区间动规转移，可以做到$O(n^2)$，稳稳拿到$40$分，代码见下。
本题的正解是在回文自动机上进行动规。
考虑回文自动机的意义：
- 一条字符为$c$的转移边，在当前回文串左右加上$c$字符。
- 后缀链接表示的串是当前串的最长回文后缀。
因此定义状态$f(i)$为在回文自动机的$i$结点时（已有$i$结点表示的回文串），已经消耗的代价。
故可以使用$n-len(i)+f(i)$更新答案。
考虑$f$的转移：
- 通过转移边两边添加字符：$f(i)\leftarrow f(fa(i))+1$，表示在上一次翻转前添加一个字符。
- 通过后缀链接直接添加前缀：$f(i)\leftarrow f(next(i))+len(i)-len(next(i))$。
- 通过$fail$链上一个长度小于当前串一半的极长回文后缀转移：$f(i)\leftarrow f(half(i))+len(i)/2-len(half(i))+1$。
事实上有更简洁的转移，第$2$个转移根本没有必要，因为可以被$3$替代。
另外，长度为奇数的串的$f$值完全不重要，因为不转移它答案不会变劣（除了直接加整个串的情况）。
注意一下细节问题，比如根的值，我的代码中都暗中处理了。
代码
Hash：$40$分。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
using namespace std;
typedef long long LL;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const LL maxn=100005,mod=1e9+7,BASE=10007;
int n,f[2005][2005];
LL Pow[maxn],L[maxn],R[maxn];
char s[maxn];
int main() {
Pow[0]=1;
for(int i=1; i<100000; i++)Pow[i]=Pow[i-1]*BASE%mod;
int t=Get_Int();
while(t--) {
scanf("%s",s+1);
n=strlen(s+1);
L[0]=1,R[n+1]=1;
for(int i=1; i<=n; i++)L[i]=(L[i-1]*BASE+(s[i]-'a'+1))%mod;
for(int i=n; i>=1; i--)R[i]=(R[i+1]*BASE+(s[i]-'a'+1))%mod;
memset(f,0,sizeof(f));
for(int i=1; i<=n; i++)f[i][i]=1;
for(int len=2; len<=n; len++)
for(int i=1; i+len-1<=n; i++) {
int j=i+len-1;
f[i][j]=min(f[i+1][j],f[i][j-1])+1;
if(len%2==0) {
int k=len/2;
LL l=(L[i+k-1]-L[i-1]*Pow[k]%mod+mod)%mod,r=(R[j-k+1]-R[j+1]*Pow[k]%mod+mod)%mod;
if(l==r)f[i][j]=min(f[i][j],f[i][i+k-1]+1);
}
}
printf("%d\n",f[1][n]);
}
return 0;
}
回文自动机：$100$分。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxn=100005;
struct Palindsome_Automaton {
int child[maxn][26];
int n,size,last,s[maxn],len[maxn],next[maxn],fa[maxn],half[maxn],f[maxn];
Palindsome_Automaton() {init();}
void init() {
size=-1;
newnode(0); //even
newnode(-1); //odd
last=n=0;
s[0]=-1;
next[0]=next[1]=1;
}
int newnode(int v) {
int now=++size;
memset(child[now],0,sizeof(child[now]));
next[now]=0;
len[now]=v;
return now;
}
void insert(int data) {
s[++n]=data;
int p=last;
while(s[n-len[p]-1]!=s[n])p=next[p];
if(!child[p][data]) {
int now=newnode(len[p]+2),q=next[p];
while(s[n-len[q]-1]!=s[n])q=next[q];
next[now]=child[q][data];
q=half[p];
while(s[n-len[q]-1]!=s[n]||len[child[q][data]]*2>len[now])q=next[q];
half[now]=child[q][data];
child[p][data]=now;fa[now]=p;
}
last=child[p][data];
}
void build(string s) {for(auto x:s)insert(x-'a');}
void dp() {
for(int i=2; i<=size; i++)f[i]=INT_MAX/2;
f[0]=1;
int ans=n;
for(int i=1; i<=size; i++) {
if(!(len[i]&1))f[i]=min(f[fa[i]]+1,f[half[i]]+len[i]/2-len[half[i]]+1);
ans=min(ans,n-len[i]+f[i]);
}
printf("%d\n",ans);
}
} pam;
char s[maxn];
int main() {
int t=Get_Int();
while(t--) {
pam.init();
scanf("%s",s+1);
pam.build(s+1);
pam.dp();
}
return 0;
}
