[Codeforces938F][DP]Erasing Substrings

翻译

给你一个长度为n的串
K次操作(K==$?{\log }_{2}n?$)
第i次操作去掉长度为$2^{i?1}$的串
求最后剩下的字典序最小的串
n<=5000

题解

显然我们可以找到一种方案
使得删去的串在原串中没有相交的情况
设$f[i][j]$表示删去后剩下的串长度为i，删除掉的长度状态为j
第二维是状压
思考我们里面要写什么
如果压一个字符串的话…暴力比较字典序复杂度$n^3\log n$
运用字典序的性质
如果对于一个$f[i][j],f[i][k]$且有$f[i][j]<f[i][k]$
显然$f[i][k]$这个状态荒废了
如此可以改为
$f[i][j]$表示… 是否是长度i的字典序最小串
转移的话扫一遍状态确定下一个字符
我们还要在当前状态删一些数为后面做准备
显然这些状态下，只要他们的某个子集是最小串，他们就是合法的
用一个高维前缀和优化即可

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<vector> #include<ctime> #include<map> #define LL long long #define mp(x,y) make_pair(x,y) using namespace std; inline int read() {
     int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
     if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
     x=x*10+ch-'0';ch=getchar();}return x*f; } inline void write(int x) {
     if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0'); } inline void print(int x){
     write(x);printf(" ");} bool ok[5005][(1<<15)+5]; int bin[25],maxpos,gg; char ch[5005]; int main() {
     bin[1]=1;for(int i=2;i<=20;i++)bin[i]=bin[i-1]<<1;scanf("%s",ch+1);int len=strlen(ch+1);for(maxpos=1;bin[maxpos+1]<=len;maxpos++);maxpos--;memset(ok,false,sizeof(ok));for(int i=0;i<bin[maxpos+1];i++)ok[0][i]=true;for(int i=1;i<=len-bin[maxpos+1]+1;i++){
     int op='z'-'a'+1;for(int j=0;j<bin[maxpos+1];j++)ok[i][j]=ok[i-1][j];for(int j=0;j<bin[maxpos+1];j++)if(ok[i][j])op=min(op,ch[i+j]-'a'+1);for(int j=0;j<bin[maxpos+1];j++)if(ok[i][j]&&ch[i+j]-'a'+1!=op)ok[i][j]=false;for(int j=0;j<bin[maxpos+1];j++)for(int k=1;k<=maxpos;k++)if(j&bin[k])ok[i][j]|=ok[i][j^bin[k]];printf("%c",op+'a'-1);}puts("");return 0; }