Erasing Substrings

一个神奇的想法是设 \(f_{i,j}\) 表示在位置 \([1,i]\) 中，我们删去了长度为 \(2^k(k\in j)\) 的一些串，所能得到的最小字典序。使用二分加哈希可以做到 \(O(n^2\log^2 n)\)，无法承受。

发现对于状态 \(f_{i,j}\)，它已经确定了 \(i-j\) 位的串，因为所有 \(\in j\) 的 \(2^k\) 之和就是 \(j\)；而依据字典序的性质，只有这 \(i-j\) 位所表示的字典序最小的那些状态，才会成为最终的答案。当然，前提是状态 \(f_{i,j}\) 合法，即剩下的部分中可以安放下尚未被删去的串。

于是我们就可以考虑直接令 \(f_{i,j}\) 表示在所有长度为 \(i-j\) 的串中，它是否是字典序最小的串之一；然后，就可以按照 \(i-j\) 递增的顺序进行 DP。你自然可以倒着复原出路径，但是更好的方法是在 DP 第 \(i-j\) 位的时候，当我们找出了这位最小能填入什么字符后，直接输出。

下面我们考虑转移。一种情况是 \(f_{i,j}\rightarrow f_{i+1,j}\) ，此时是第 \(i+1\) 位被保留下来，因此这个转移的前提是第 \(i+1\) 位上可以填入最小的字符；

还有一种情况就是第 \(i+1\) 位被删去，于是我们枚举 \(k\notin j\)，直接转移即可。

注意到代码实现与此处描述有一些区别，描述中的递推式是刷表法，而代码中的递推式是填表法；同时，代码中的 DP 顺序上文已经提到，\(i-j\) 递增的顺序。

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+100;
int n,m,all;
bool f[N][N];
char s[N];
int main(){
    scanf("%s",s+1);
	n=strlen(s+1);
    while((2<<m)<=n) m++;
	all=(1<<m);
    for(int i=0;i<all;i++) f[i][i]=1;
    for(int i=1;i<=n-all+1;i++){
        char lim=127;
        for(int j=i;j<i+all;j++) if(f[j-1][j-i]) lim=min(lim,s[j]);
        putchar(lim);
        for(int j=i;j<i+all;j++) f[j][j-i]=(f[j-1][j-i]&&(s[j]==lim));
        for(int j=i;j<i+all;j++){
			for(int k=0;k<m;k++){
				if((j-i)&(1<<k)) f[j][j-i]|=f[j-(1<<k)][j-i-(1<<k)];
			}
		}
    }
    return 0;
}