[BZOJ4565][HAOI2016]字符合并(区间状压DP)

https://blog.****.net/xyz32768/article/details/81591955

首先区间DP和状压DP是比较明显的，设f[L][R][S]为将[L,R]这一段独立操作最终得到的字符序列为S的最大收益。其中S的位数为(R-L)%(k-1)+1。

枚举R第一次参与的操作的左端点mid与这次操作得到的数转移，若当前长度为k则要加上当前操作收益。

注意这个mid和R的距离一定是k-1的倍数，这样总状态和转移就很少，于是可以$O(n^32^8)$通过。

 #include<cstdio>
 #include<cstring>
 #include<algorithm>
 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 typedef long long ll;
 using namespace std;

 const int N=;
 const ll inf=1e14;
 int n,k,a[N],c[N],w[N];
 ll ans,f[N][N][N];
 char s[N];

 int main(){
     freopen("bzoj4565.in","r",stdin);
     freopen("bzoj4565.out","w",stdout);
     scanf("%d%d%s",&n,&k,s+);
     rep(i,,n) a[i]=s[i]-'';
     for (int i=; i<(<<k); i++) scanf("%d%d",&c[i],&w[i]);
     rep(i,,n) rep(j,,n) rep(z,,(<<k)) f[i][j][z]=-inf;
     rep(i,,n) f[i][i][a[i]]=;
     rep(l,,n) rep(i,,n-l+){
         int j=i+l-,len=j-i;
         while (len>k-) len-=k-;
         for (int mid=j; mid>i; mid-=k-)
             for (int z=; z<(<<len); z++){
                     f[i][j][z<<]=max(f[i][j][z<<],f[i][mid-][z]+f[mid][j][]);
                     f[i][j][(z<<)|]=max(f[i][j][(z<<)|],f[i][mid-][z]+f[mid][j][]);
                 }
         if (len==k-){
             ll g[]; g[]=g[]=-inf;
             for (int z=; z<(<<k); z++) g[c[z]]=max(g[c[z]],f[i][j][z]+w[z]);
             f[i][j][]=g[]; f[i][j][]=g[];
         }
     }
     for (int i=; i<(<<k); i++) ans=max(ans,f[][n][i]);
     printf("%lld\n",ans);
     return ;
 }