洛谷。
题面
初始状态为全是 \(0\)，将某一为变化的前提是当前节点的前缀（不包括当前节点）是 \(s\) 串的一个后缀，每次变化需要 \(1\) 的代价。问最后要使所有都为 \(1\) 的最小代价。
分析
很有意思的一道题，感觉玩起来跟喵了个喵一样上头。
首先，我们肯定是要先让 \(n\) 这个位置变成 \(1\)，然后再将前边的第一个是 \(0\) 的变成 \(1\)，反复进行该操作。
我们令 \(t_i\) 表示要将 \(i\) 这个位置翻转的前缀，后面的位置用 \(0\) 补全至长度为 \(n\)。
再看要使 \(i\) 这个位置翻转的方案，是由当前的第一个与 \(t_i\) 不同的节点 \(j\) 开始，将当前的前缀变成 \(t_j\) ，翻转 \(j\)，继续寻找不同。
我们可以发现啊，我们的每次操作其实都是从某一个前缀变成另一个前缀，由此，我们可以设计出我们的第一个状态与第一个 dfs，\(f_{i,j}\) 表示从 \(t_i\) 变成 \(t_j\) 的最小代价。
inline int dfs(int u,int v) {
if(~f[u][v]) return f[u][v];
int tot=1,x=u;
for(int now=v-1; now; --now) {
if(s[x][now]!=s[v][now]) {
ADD(tot,dfs(x,now));
x=now;
}
}
return f[u][v]=tot;
}
时间复杂度：\(O(n^3)\)，拿下 \(56pts\)。
优化
我们从代码上分析一下，我们的代价实质上是做了什么计算呢，对于计算 \(dfs(i,j)\)，我们令不断枚举中的数字分别为 \(st_1=u\)，\(st_2\)，\(\dots\)，\(st_{top}\)，\(dfs(i,j)=1+\sum f_{st_i,st_{i+1}}\)。
我们有一部分是反复计算的，考虑将这一部分进行记忆化，而我们的这一部分，则是与 \(v\) 相比较的。由此，设计出一个辅助的转移的数组 \(g_{i,j}\)，\(g_{i,j}\) 表示从 \(i\) 开始的与 \(j\) 比较所计算出来的值。
inline int redfs(int u,int v) {
if(~g[u][v]) return g[u][v];
int tot=0;
for(int now=u-1; now; --now) {
if(s[u][now]!=s[v][now]) {
ADD(tot,dfs(u,now)+redfs(now,v));
break;
}
}
return g[u][v]=tot;
}
inline int dfs(int u,int v) {
if(~f[u][v]) return f[u][v];
int tot=1;
for(int now=v-1; now; --now) {
if(s[u][now]!=s[v][now]) {
ADD(tot,dfs(u,now)+redfs(now,v));
break;
}
}
return f[u][v]=tot;
}
由此，我们的 \(O(n^3)\) 得到了极大的优化，可以通过此题。
剩下就需要优化我们的扫描上，有一种思路，我们可以使用字符串哈希加二分来处理，时间复杂度：\(O(n^2\times \log n)\)，时间复杂度计算上勉强可以过。
另一种想法，我们可以利用我们的字符串的性质，我们的字符串都是同一个字符串的后缀，由此，我们可以预处理我们的扫描，时间复杂度：\(O(n^2)\)。