记录编号	438154	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2016]字符合并	最终得分	100
用户昵称	HZOI_蒟蒻一只	是否通过	通过
代码语言	C++	运行时间	1.417 s
提交时间	2017-08-15 15:24:06	内存使用	5.01 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=305,maxa=1<<9;
long long f[maxn][maxn][2],c[maxn],v[maxn],a[maxn],g[maxn][maxa],now,tmp[3],ans[maxn];
/*我们这里的f数组与其他的f数组并不完全相同，这里的f数组第三；严格地讲只是半维，0/1表示这个串全部变为0/1可以获得的最大积分，
相应的g数组第二维从半维变成整维，第二维代替了f数组本应该存在的存储最近8位状态的第三维，g数组也就改变了意义，g[i][j]变为转移到i这个长度，状态为j下最大收益；
然后，这个tmp数组中的tmp[i]也就表示了所有可以转化到i的01串转化后连带前面的串可以获得的最大收益。*/
int N,K;
int haha()
{
    freopen("merge_2016.in","r",stdin);
    freopen("merge_2016.out","w",stdout);
    scanf("%d%d",&N,&K);//输入
    int att=(1<<K);//确定最大状态
    memset(f,-1,sizeof(f));//初始化记忆化表格
    for(int i=1;i<=N;i++)//输入01串
    {
        scanf("%1d",&a[i]);
        f[i][i][a[i]]=0;//已经合适，就不需要修改
    }
    for(int i=0;i<att;i++)scanf("%d%d",&c[i],&v[i]);//每一种修改的情况
    for(int i=N-K+1;i>=1;i--)//可以搞这么多轮，从后往前合并
    {
        memset(g,-1,sizeof(g));//初始化
        now=1;g[i][0]=f[i][i][0];g[i][1]=f[i][i][1];//从i开始的串最后一位状态为0、1的情况已经确定了
        for(int j=i+1;j<=N;j++)
        {
            for(int s=0;s<(1<<now);s++)//枚举状态
                if(g[j-1][s]>=0)//这一状态是合法的
                    for(int k=j;k<=N;k+=K-1)//每k个为一段判断
                    {
                        if(f[j][k][0]>=0)g[k][s<<1]=max(g[k][s<<1],g[j-1][s]+f[j][k][0]);//可以合成0就合成0
                        if(f[j][k][1]>=0)g[k][s<<1|1]=max(g[k][s<<1|1],g[j-1][s]+f[j][k][1]);//可以合成1就合成1，其实这里就是一个区间dp
                    }
            if(++now==K)//长度够了
            {
                tmp[0]=tmp[1]=-1;//初始化转化到尾巴的情况
                for(int k=0;k<(1<<now);k++)
                    if(g[j][k]>=0)tmp[c[k]]=max(tmp[c[k]],v[k]+g[j][k]);//这个状态是可以构建出来的，就更新以目标字符结尾的结果
                f[i][j][1]=g[j][1]=tmp[1];//更新结果
                f[i][j][0]=g[j][0]=tmp[0];
                now=1;
            }
        }
    }
    for(int i=1;i<=N;i++)
        for(int j=i;j<=N;j+=K-1)ans[j]=max(ans[j],ans[i-1]+max(f[i][j][1],f[i][j][0]));//每一个都可以合并，能合就合
    printf("%lld\n",ans[N]);
}
int sb=haha();
int main(){;}