BZOJ 4565: [Haoi2016]字符合并

Description

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

Input

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

Output

输出一个整数表示答案

Sample Input

3 2
101
1 10
1 10
0 20
1 30

Sample Output

40

HINT

第3行到第6行表示长度为2的4种01串合并方案。00->1,得10分,01->1得10分,10->0得20分,11->1得30分。

Solution

状态压缩DP。

MZX课件上的题目。
* f[l,r,S]=max{f[l,k,0/1]+f[k+1,r,s]}
* O(n^3/k*2^k)
(PS:就给了两行怎么看啊QAQ。。。)

首先要弄懂一点,区间[l,r]要变成S,最优的决策一定可以表示为把后k个字符变成0/1,然后把前r-l+1-k个字符变为S>>1来达到。

这样dp式子就不难了,之后就是恶心的细节了。。

要搞懂两条:
1. 同一个S可能表示多个不同的状态,S=0时可以表示0和00,如何规避掉这个问题?
2. l,r要变成一个长度为1的区间时,如何计算w对答案的贡献?

带着问题去翻了翻神犇的Blog。。。传送门

然后豁然开朗。
1. 首先我们可以用已有的状态的信息来更新没有的状态的信息,然后再更新的时候保证左右两边的都是合法的(这个比较容易实现,控制分给左右区间长度即可 因为合法的Llen Rlen都是一一对应的),这样就解决了问题1;
2. 对于问题2,我们想如果已经统计了能达到l,r的状态对l,r的贡献(抛开最后的那一次合并)了的话,只需要考虑最后那一次合并合并的是什么就好了。

Orz。。。

Code

#include <map>
#include <set>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

const LL INF = 1000000007ll*1000000007ll;
const int maxn = 305;

inline int getint() {
    int r = 0; bool b = true; char c = getchar();
    while ('0' > c || c > '9') {if (c == '-') b = false; c = getchar();}
    while ('0' <= c && c <= '9') {r = r * 10 + (c - '0'); c = getchar();}
    if (b) return r;
    return -r;
}
LL tmp[2], f[maxn][maxn][1<<8], w[1<<8];
int n, K, len[maxn], c[1<<8];
char str[maxn];
int main() {
    n = getint(); K = getint();
    for (int i = 1; i < K; ++i) len[i] = i;
    for (int i = K; i <= n; ++i) len[i] = len[i-K+1];
    scanf("%s", str+1);
    for (int i = 0; i < 1<<K; ++i) {
        c[i] = getint();
        w[i] = getint();
    }
    for (int i = 0; i < maxn; ++i)
        for (int j = 0; j < maxn; ++j)
            for (int k = 0; k < 256; ++k)
                f[i][j][k] = -INF;
    for (int i = 1; i <= n; ++i)
        f[i][i][str[i]-'0'] = 0;
    for (int l = 2; l <= n; ++l)
        for (int i = 1, j = i+l-1; j <= n; ++i, ++j) {
            for (int s = 0; s < 1<<len[l-1]; ++s) {
                for (int k = j; k > i; k -= K-1) {
                    if (f[i][k-1][s] == -INF) continue;
                    if (f[k][j][0] != -INF) f[i][j][s<<1] = max(f[i][j][s<<1], f[i][k-1][s] + f[k][j][0]);
                    if (f[k][j][1] != -INF) f[i][j][s<<1|1] = max(f[i][j][s<<1|1], f[i][k-1][s] + f[k][j][1]);
                }
            }
            if (len[l] == 1) {
                tmp[0] = tmp[1] = -INF;
                for (int s = 0; s < 1<<K; ++s)
                    tmp] = max(tmp], f[i][j][s] + w[s]);
                f[i][j][0] = tmp[0];
                f[i][j][1] = tmp[1];
            }
        }
    LL ans = 0;
    for (int i = 0; i < 1<<K; ++i)
        ans = max(ans, f[1][n][i]);
    printf("%lld", ans);
}
  1. MagHSK说道:

    评论测试

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据