题意：
给一个长度为n的字符串，定义$k=floor{log_2 n}$
一共k轮操作，第i次操作要删除当前字符串恰好长度为$2^{i-1}$的子串
问最后剩余的字符串字典序最小是多少？
分析：
首先很容易得到一个性质，那就是删除的那些串是可以不交叉的
很容易想到一个很简单的dp
dp[i][j]表示考虑原串的前i位，删除状态为j的情况下字典序最小的字符串（注意dp里面保存的是个字符串）
那么很明显就是个O(n^3logn)的dp，无法通过
dp里是一个字符串这个东西是很浪费时间而且很不优美的
根据题解的做法，重新设计状态
dp[i][j]表示已经确定了最终字符串的前i位，目前删除情况为j的情况下，字典序最小的字符串
这样设计状态我们会发现一个性质，那就是如果dp[i][j]<dp[i][k]，那么dp[i][k]就不起作用了
所以dp数组可以用bool值来表示该状态是否为当前最小的字符串
更新状态的话，根据确定位数i和删除位数j就知道那些"1"对应字符串的下一位是多少了，更新新的最小字符串
然后我们要考虑当前阶段给后面要删除几个数，这里即使要求满足若一个状态的某个子集是真，那么它就是真
这用一个高维前缀和解决即可
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=5000; 4 char s[maxn+5]; 5 bool dp[maxn+5][maxn+5]; 6 int n,l,m; 7 string ans; 8 int main() 9 { 10 scanf("%s",s); 11 n=strlen(s); 12 l=0; 13 while((1<<(l+1))<=n) ++l; 14 m=1<<l; 15 for(int j=0;j<m;++j) 16 dp[0][j]=1; 17 for(int i=1;i<=n-m+1;++i) 18 { 19 for(int j=0;j<m;++j) dp[i][j]=dp[i-1][j]; 20 char mi='z'; 21 for(int j=0;j<m;++j) 22 if(dp[i-1][j]) mi=min(mi,s[i-1+j]); 23 for(int j=0;j<m;++j) 24 if(dp[i][j]&&s[i-1+j]!=mi) dp[i][j]=0; 25 26 for(int j=0;j<m;++j) 27 for(int k=0;k<l;++k) 28 if(j&(1<<k)) dp[i][j]|=dp[i][j^(1<<k)]; 29 ans=ans+mi; 30 31 } 32 cout<<ans<<endl; 33 }