title

BZOJ 4565

LUOGU 3736

Description

有一个长度为 n 的 01 串，你可以每次将相邻的 k 个字符合并，得到一个新的字符并获得一定分数。得到的新字符和分数由这 k 个字符确定。你需要求出你能获得的最大分数。

Input

第一行两个整数 \(n,k\)。

接下来一行长度为 \(n\) 的 \(01\) 串，表示初始串。

接下来 \(2^k\) 行，每行一个字符 \(c_i\) 和一个整数 \(w_i\)，\(c_i\) 表示长度为 \(k\) 的 \(01\) 串连成二进制后按从小到大顺序得到的第 \(i\)种合并方案得到的新字符， \(w_i\)表示对应的第 \(i\) 种方案对应获得的分数。\(1\leqslant n\leqslant 300,0\leqslant c_i\leqslant 1,w_i\geqslant 1,k\leqslant 8\)

Output

输出一个整数表示答案

Sample Input

3 2
1 0 1
1 10
1 10
0 20
1 30

Sample Output

40

HINT

第 3 行到第 6 行表示长度为 2 的 4 种 01 串合并方案。

\(00\to 1\) 得10分，\(01\to 1\) 得10分，\(10\to 0\) 得20分，\(11\to 1\) 得30分。

analysis

一看到 \(k\leqslant 8\)，你想到了什么，又看到了字符串合并，你又想到了什么，这时候，就要相信一句话：大胆假设，不用证明。

不错，正解就是 区间 \(Dp~+~\) 状压 \(Dp\)。

设 \(f[i][j][t]\)表示原串中第 \(i\) 到 \(j\) 个数字最终合并成 \(t\) 的状态的最大分数。

我们枚举中间的断点 \(mid(i\leqslant mid\leqslant j)\)，因为我们可以证明区间不相交，所以不妨使 \(mid\) 右边的子串合并成 \(t\) 的最后一位数字，\(mid\) 左边的合并成其他位的数字。 因为能合并成 \(1\) 位数字的原串长度可以为 \(1,k,2k-1...\)，所以我们每次将 \(mid\) 的值改变 \(k-1\) 即可。

所以，状态转移方程为
\[ f[i][j][k<<1]=\max(f[i][j][k<<1],f[i][mid-1][k]+f[mid][j][0]); \]

\[ f[i][j][k<<1|1]=\max(f[i][j][k<<1|1],f[i][mid-1][k]+f[mid][j][1]); \]

另有一种特殊情况，即 \(i\) 到 \(j\) 恰好有 \(k\) 位数字，我们直接把它合并一次。用一个辅助数组存储最大值（直接修改 \(f[i][j][t]\) 可能会导致修改后的数 会再修改其他数组元素）。

那么最终答案就是：
\[ ans=\max\{f[1][n][所有状态]\} \]

code

#include<bits/stdc++.h>

typedef long long ll;
const ll maxn=305,maxk=8,inf=1ll<<60;

namespace IO
{
    char buf[1<<15],*fs,*ft;
    inline char getc() { return (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs))?0:*fs++; }
    template<typename T>inline void read(T &x)
    {
        x=0;
        T f=1, ch=getchar();
        while (!isdigit(ch) && ch^'-') ch=getchar();
        if (ch=='-') f=-1, ch=getchar();
        while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
        x*=f;
    }

    char Out[1<<24],*fe=Out;
    inline void flush() { fwrite(Out,1,fe-Out,stdout); fe=Out; }
    template<typename T>inline void write(T x)
    {
        if (!x) *fe++=48;
        if (x<0) *fe++='-', x=-x;
        T num=0, ch[20];
        while (x) ch[++num]=x%10+48, x/=10;
        while (num) *fe++=ch[num--];
        *fe++='\n';
    }
}

using IO::read;
using IO::write;

ll a[maxn],c[1<<maxk],w[1<<maxk],f[maxn][maxn][1<<maxk],g[2];
template<typename T>inline T max(T a,T b) { return a>b ? a : b; }

int main()
{
    ll n,K;read(n);read(K);
    for (ll i=1; i<=n; ++i) scanf("%1lld",&a[i]);//read(a[i);坑点，不然BZOJ会TLE
    for (ll i=0; i<(1<<K); ++i) read(c[i]),read(w[i]);

    for (ll i=1; i<=n; ++i)
        for (ll j=i; j<=n; ++j)
            for (ll k=0; k<(1<<K); ++k) f[i][j][k]=-inf;

    for (ll i=n; i>=1; --i)//注意循环的正逆顺序：mid<j，正序枚举j；mid>i，倒序枚举i
        for (ll j=i; j<=n; ++j)
        {
            if (i==j)
            {
                f[i][j][a[i]]=0;
                continue;
            }
            ll len=j-i;//前一段得到的长度
            len%=K-1;
            if (!len) len=K-1;
            for (ll mid=j; mid>i; mid-=K-1)//能够得到1位的位数相差K-1
                for (ll k=0; k<(1<<len); ++k)//更新产生的状态
                {
                    f[i][j][k<<1]=max(f[i][j][k<<1],f[i][mid-1][k]+f[mid][j][0]);
                    f[i][j][k<<1|1]=max(f[i][j][k<<1|1],f[i][mid-1][k]+f[mid][j][1]);
                }
            if (len==K-1)//加上一次操作的分数要单独讨论
            {
                g[0]=g[1]=-inf;
                for (ll k=0; k<(1<<K); ++k) g[c[k]]=max(g[c[k]],f[i][j][k]+w[k]);//这个地方是K位
                f[i][j][0]=g[0],f[i][j][1]=g[1];//用临时数组更新
            }
        }

    ll ans=-inf;
    for (ll i=0; i<(1<<K); ++i) ans=max(ans,f[1][n][i]);

    write(ans);
    IO::flush();
    return 0;
}