【题意】

【算法】区间DP+状压DP

【题解】

---

题外话：

区间DP的状态转移特点是一次转移只做一次合并，小合并由小区间做好传递，这样就能处理好复杂的区间问题。

数据范围k这么小而且和01有关，果断状压啊。

---

引用自： by zyf2000

下面过程中的状态S都是前面的0补齐的！

f[i][j][S]表示区间i~j状态为S的最大价值，显然对于一个区间，其状态长度len(S)<=k是唯一确定的（只要留够下一次合并的长度就够了，而留k是为了后面处理全区间直接合并）。

对于区间i~j，长度len(S)的计算方式：

考虑转移：

①划分转移

直接考虑在中间划分成两半来组合是没有意义的，会重复枚举，而且复杂度O(n^2*[n*2^(2*k)])难以接受。（”[]“中是转移复杂度）

其实划分转移需要找到一种不重不漏的划分方式，只要满足不重不漏怎么划分都是无所谓的。

对于一个状态S，我们分成S'+0/1，考虑枚举右边若干位的状态为0/1，再枚举左边剩余位的状态S‘，拼成状态S。

这样首先不重不漏(对于每个S的方案只枚举一次且一定会枚举到），且无效状态的数量可以承受，复杂度O(n^2*[n*2^k])。

②直接合并：对于区间长度len(S)=k要直接合并成f[i][j][0/1]。

具体的转移方程见上面zyf2000的博客。

细节：len(S')=len(S)-1，枚举右边若干位的方法是从1开始，每次加k-1（每次凑成k个后变成1个）。

对于一个区间状态长度唯一确定，所以其实在划分转移中，对于一个区间的访问长度都是一定的，不可能出现变动，只要访问到某个区间就一定是某个长度不需要人为限制的。

#include
      
       #include
       
        #include
        
         #define ll long longusing namespace std;const int maxn=310,maxS=1<<8;int n,k,c[maxS];ll w[maxS],f[maxn][maxn][maxS],g[2];char s[maxn];int main(){    scanf("%d%d%s",&n,&k,s+1);    for(int i=0;i<(1<
         
          k)len-=k-1;            for(int x=j;x>i;x-=k-1){                for(int S=0;S<(1<<(len-1));S++)if(~f[i][x-1][S]){                    if(~f[x][j][0])f[i][j][S<<1]=max(f[i][j][S<<1],f[i][x-1][S]+f[x][j][0]);                    if(~f[x][j][1])f[i][j][S<<1|1]=max(f[i][j][S<<1|1],f[i][x-1][S]+f[x][j][1]);                }            }            if(len==k){                g[0]=g[1]=-1;                for(int S=0;S<(1<
         
        
       
      

 

 

upd：

区间DP，设$f_{i,j}(S)$表示区间[i,j]状态为S的答案（这其实就是最终答案的表示方式）。对于一个给定区间，消除完成后的长度是确定的且<k，可以通过while(len>k)len-=k-1得到。（不消除到k以内的方案可以通过枚举其它区间转移得到，这里不用考虑）

考虑划分转移，枚举最后一个字符的来源区间转移，这样会依次转移下去。（中间合并会从后面一个一个枚举得到）

然后处理一下恰好k的时候，并成1个。