一个区间缩小变换的问题，并且n<=300

启示我们区间dp

 

我们考虑最后一定是在原串上扣一些，剩一些

所以不妨前求出[l,r]把[l,r]完全处理成什么样子的方案数

然后再来一遍序列dp，统计答案

（并且发现，每次消除其实是减去k-1个，换句话说，对于l,l+k-1,l+2k-1，消除一次之后，还可以再消除，直到最后剩一个，所以考虑关于mod(k-1)的同余位置）

关于g对f的转移，就是我们考虑[l,r]最后一次是从什么消过来的

关于g自己的转移，考虑最后一部分会消成什么样。（最后一个位置不消掉，就是从f[r][r][0/1]转移过来）

代码：

#include
     
      #define il inline#define reg register int#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=303;const ll inf=0x3f3f3f3f3f3f3f3f;ll f[303][303][2],g[303][10][1<<8],h[303];int a[N];int c[1<<8],w[1<<8];int n,k;int main(){    rd(n);rd(k);    for(reg i=1;i<=n;++i) rd(a[i]);    for(reg i=0;i<(1<
      
       =1;--l){        for(reg i=l-1;i<=n;++i){            memset(g[i],0xcf,sizeof g[i]);        }        g[l-1][0][0]=0;        g[l][1][a[l]]=0;        for(reg r=l;r<=n;++r){            for(reg i=r;i>l;i-=(k-1)){                for(reg t=1;t<=k&&t<=i-l+1;++t){                    for(reg s=0;s<(1<<(t-1));++s){                        g[r][t][s<<1]=max(g[r][t][s<<1],g[i-1][t-1][s]+f[i][r][0]);                        g[r][t][s<<1|1]=max(g[r][t][s<<1|1],g[i-1][t-1][s]+f[i][r][1]);                    }                }            }            if((r-l)%(k-1)==0){                for(reg s=0;s<(1<
       
        =1;j-=(k-1)){            h[i]=max(h[i],h[j-1]+f[j][i][0]);            h[i]=max(h[i],h[j-1]+f[j][i][1]);        }    }    printf("%lld\n",h[n]);    return 0;}}signed main(){    freopen("3.in","r",stdin);    freopen("3.out","w",stdout);    Miracle::main();    return 0;}/*   Author: *Miracle*   Date: 2019/2/9 18:19:41*/
       
      
     

就是考虑“统计消去[l,r]的”，再来一次统计“在原序列上消去”