洛谷 3736 bzoj 4565 libreoj 2063 [HAOI2016]字符合并 题解

发表于 | 更新于 | 阅读次数：
本文字数： 1k 字 | 阅读时长 ≈ 5 分钟

题意简述

长度为n（<=300）的01串，你能合并连续一段长度为k（k<=8）的子串。会合并成什么，得到多少分数，由映射表决定。
比如说，映射表是

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

就代表

1
2
3
4
00->1，得分是10
01->1，得分是10
10->0，得分是20
11->1，得分是30

合理分配合并方案，使得得分最大。

思路框架

区间DP+状压DP

具体思路

观察到wi都是正的，所以我们肯定是把一段区间合并到不能合并才是最优的。

我们每次拿$k$个换一个（前提是有$k$个），所以每次会减少$k-1$个。区间里总共有r-l+1个，所以应该是最后合并出来的长度len=(r-l+1)/(k-1)。前驱状态长度就是len-1个。这个-1千万要注意了，如果(r-l+1)%(k-1)==0，那len就是-1了。所以，当len<=0的时候，记得给他加上一个k-1。

设dp[l][r][s]表示l到r合并成状态s的最大得分。我们枚举断点mid和前驱状态s’，s’=s/2。但是s的最后一位是0/1需要分类讨论。而且满足[l,mid]合并出来的长度为len。解个方程，mid和r关于k-1同余。

我们把l到mid合并成s’，把mid+1到r合并成0/1，来更新dp[l][r][2s’+0/1]的方案。

你以为这就结束了？如果len==k-1，说明原区间的len=k，即，珂以合并完。那么此时我们就是少考虑一个转移，把这种情况特判上。我们枚举最后合并出的状态，计算得分，更新dp。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define int long long
    #define N 322
    #define S 8
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Rd(int cnt,...)
    {
        va_list args;
        va_start(args,cnt);
        F(i,1,cnt)
        {
            int* x=va_arg(args,int*);R1(*x);
        }
        va_end(args);
    }

    int a[N];
    int n,k;
    int c[N],w[N];
    void Input()
    {
        Rd(2,&n,&k);
        F(i,1,n) scanf("%1lld",&a[i]);
        F(i,0,(1<<k)-1) Rd(2,&c[i],&w[i]);
    }

    int to_2(char s[]){int ans=0;for(int i=0;s[i];++i) ans=((ans<<1)|(a[i])); return ans;}
    int range_to2(int l,int r){int ans=0;F(i,l,r) ans=((ans<<1)|(a[i])); return ans;}
    int dp[N][N][1<<S];
    void Soviet()
    {
        MEM(dp,0xcf);
        
        D(l,n,1) F(r,l,n)
        {
            if (l==r) {dp[l][r][a[l]]=0;continue;} //这个是显然的，又是边界
            
            int len=(r-l+1)%(k-1)-1;
            if (len==-1) len=k-2;
            
            if (len==0) len=k-1; //这两句话注意次序，因为k-2珂能等于0。此时我们两个if都要被执行到
            Ds(mid,r,l+1,mid-=k-1) F(o,0,(1<<len)-1)
            {
                dp[l][r][o<<1]=max(dp[l][r][o<<1],dp[l][mid-1][o]+dp[mid][r][0]);
                dp[l][r][o<<1|1]=max(dp[l][r][o<<1|1],dp[l][mid-1][o]+dp[mid][r][1]);
                //区间分两半更新答案
            }
            if (len==k-1) //特判最后还有一次合并的情况
            {
                int g[2];MEM(g,0xcf);
                //最后剩下0/1分类讨论
                F(o,0,(1<<k)-1) //o：合并成什么状态
                {
                    g[c[o]]=max(g[c[o]],dp[l][r][o]+w[o]);
                }
                dp[l][r][0]=g[0];
                dp[l][r][1]=g[1];
            }
        } 
        printf("%lld\n",*max_element(dp[1][n],dp[1][n]+(1<<k)));
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
    #undef int //long long
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w