codeforces 938F（dp+高维前缀和）

题意：

　　给一个长度为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"对应字符串的下一位是多少了，更新新的最小字符串

　　然后我们要考虑当前阶段给后面要删除几个数，这里即使要求满足若一个状态的某个子集是真，那么它就是真

　　这用一个高维前缀和解决即可

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=;

 char s[maxn+];

 bool dp[maxn+][maxn+];

 int n,l,m;

 string ans;

 int main()

 {

     scanf("%s",s);

     n=strlen(s);

     l=;

     while((<<(l+))<=n) ++l;

     m=<<l;

     for(int j=;j<m;++j)

     dp[][j]=;

     for(int i=;i<=n-m+;++i)

     {

         for(int j=;j<m;++j) dp[i][j]=dp[i-][j];

         char mi='z';

         for(int j=;j<m;++j)

             if(dp[i-][j]) mi=min(mi,s[i-+j]);

         for(int j=;j<m;++j)

             if(dp[i][j]&&s[i-+j]!=mi) dp[i][j]=;

         for(int j=;j<m;++j)

             for(int k=;k<l;++k)

                 if(j&(<<k)) dp[i][j]|=dp[i][j^(<<k)];

         ans=ans+mi;

     }

     cout<<ans<<endl;

 }

巴特西

codeforces 938F（dp+高维前缀和）

最新文章

热门文章