「BZOJ 4565」「HAOI 2016」字符合并「区间状压DP」

ゝ一世哀愁。 2023-08-17 17:31 138阅读 0赞

**题意**

给一个长度为\\(n(\\leq 300)\\)的\\(01\\)串，每次可以把\\(k(\\leq 8)\\)个相邻字符合并，得到新字符和一定分数，最大化最后的得分

**题解**

考虑设计dp：\\(dp\[S\]\[i\]\[j\]\\)表示区间\\(\[i, j\]\\)合并为\\(S\\)，最大得分是多少。

这么考虑一定是不遗漏的。如果\\(\[i, j\]\\)留下来的区间长度\\(>k\\)，那这个合并方案一定会在包含它的大区间计算到，所以我们只考虑能合并都合并完的情况

枚举缩完最后一个位是啥，这对应\\(\[i, j\]\\)的一个长度\\(\\bmod k-1\\)为\\(1\\)后缀

然后再考虑这个区间缩成一个字符的情况。由于顺序混乱（比如\\(0\\)更新\\(1\\)，\\(1\\)又更新\\(0\\)），拿临时数组存，最后再赋值回去

#include <algorithm>
    #include <cstring>
    #include <cstdio>
    using namespace std;
    
    typedef long long ll;
    
    const int N = 310;
    
    int n, k, c[1 << 8], la[N];
    ll w[1 << 8], g[2], dp[1 << 8][N][N];
    char s[N];
    
    void upd(ll &x, ll y) { x = max(x, y); }
    
    int main() {
        scanf("%d%d%s", &n, &k, s + 1);
        for(int i = 0; i < (1 << k); i ++) scanf("%d%lld", c + i, w + i);
        for(int i = 1, j; i <= n; i ++) {
            for(j = i; j >= k; j = j - k + 1);
            la[i] = j;
        }
        memset(dp, -1, sizeof dp);
        for(int i = 1; i <= n; i ++) dp[s[i] -= '0'][i][i] = 0;
        for(int i = n - 1; i >= 1; i --) {
            for(int j = i + 1; j <= n; j ++) {
                for(int u = j; u > i; u -= k - 1) {
                    for(int S = 0; S < (1 << la[u - i]); S ++) if(~ dp[S][i][u - 1]) {
                        if(~ dp[0][u][j]) upd(dp[S << 1][i][j], dp[S][i][u - 1] + dp[0][u][j]);
                        if(~ dp[1][u][j]) upd(dp[S << 1 | 1][i][j], dp[S][i][u - 1] + dp[1][u][j]);
                    }
                }
                if(la[j - i + 1] == 1) {
                    g[0] = g[1] = -1;
                    for(int S = 0; S < (1 << k); S ++) if(~ dp[S][i][j]) {
                        upd(g[c[S]], dp[S][i][j] + w[S]);
                    }
                    dp[0][i][j] = g[0]; dp[1][i][j] = g[1];
                }
            }
        }
        ll ans = -1;
        for(int S = 0; S < (1 << (k - 1)); S ++)
            upd(ans, dp[S][1][n]);
        printf("%lld\n", ans);
        return 0;
    }

转载于:https://www.cnblogs.com/hongzy/p/11334843.html