BZOJ 1068: [SCOI2007]压缩

\(dp_{i,j,0}\) 表示 \([i,j]\) 中不包含 \(M\) 的最优值
\(dp_{i,j,1}\) 表示 \([i,j]\) 中包含若干个 \(M\) 的最优值
\(dp_{i,j,0}=\min\{dp_{i,k,0}+j-k\}\)
若 \([i,j]\) 是一个复制的串，\(dp_{i,j,0}=\min\{dp_{i,mid,0}+1\}\)
\(dp_{i,j,1}=\min\{dp_{i,k,1}+dp_{k+1,j,1}+1\}\)
\(+1\) 表示在位置 \(k\) 放置一个 \(M\)

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define Edg int cnt=1,head[N],to[N*2],ne[N*2];void addd(int u,int v){to[++cnt]=v;ne[cnt]=head[u];head[u]=cnt;}void add(int u,int v){addd(u,v);addd(v,u);}
#define Edgc int cnt=1,head[N],to[N*2],ne[N*2],c[N*2];void addd(int u,int v,int w){to[++cnt]=v;ne[cnt]=head[u];c[cnt]=w;head[u]=cnt;}void add(int u,int v,int w){addd(u,v,w);addd(v,u,w);}
#define es(u,i,v) for(int i=head[u],v=to[i];i;i=ne[i],v=to[i])

const int N = 55;
char str[N];
int dp[N][N][2];

bool check(int x, int y) {
    int len = y - x + 1;
    if (len & 1) return 0;
    for (int i = x; i < x + len / 2; i++)
        if (str[i] != str[i + len / 2]) return 0;
    return 1;
}

int main() {
    scanf("%s", str);
    int n = strlen(str);
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 0; i < n; i++) dp[i][i][0] = dp[i][i][1] = 1;
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len <= n; i++) {
            int j = i + len - 1;
            for (int k = i; k < j; k++) {
                dp[i][j][0] = std::min(dp[i][j][0], dp[i][k][0] + j - k);
                dp[i][j][1] = std::min(dp[i][j][1], dp[i][k][1] + dp[k + 1][j][1] + 1);
            }
            if (check(i, j)) dp[i][j][0] = std::min(dp[i][j][0], dp[i][i + len / 2 - 1][0] + 1);
            dp[i][j][1] = std::min(dp[i][j][1], dp[i][j][0]);
        }
    }
    printf("%d\n", dp[0][n - 1][1]);
    return 0;
}

BZOJ 1068: [SCOI2007]压缩

原文：https://www.cnblogs.com/Mrzdtz220/p/12331322.html