M_sea

洛谷2470 [SCOI2007]压缩
LuoguBZOJ分析状态设置很奇妙的一道DP题。设$f[i][j][0/1]$表示$i\sim j$,压缩后没有...
扫描右侧二维码阅读全文
05
2019/02

洛谷2470 [SCOI2007]压缩

Luogu

BZOJ

分析

状态设置很奇妙的一道DP题。

设$f[i][j][0/1]$表示$i\sim j$,压缩后没有/有M的最短压缩长度。

然后有$f[i][j][0]=\min\limits_{k=i}^{j-1}\left\{f[i][k][0]+j-k\right\}$,$f[i][j][1]=\min\limits_{k=i}^{j-1}\Big\{\min\{f[i][k][0],f[i][k][1]\}+\min\{f[k+1][j][0],f[k+1][j][1]\}+1\Big\}$

注意特判$i\sim j$为ABAB这种串的情况,此时$f[i][j][0]=f[i][(i+j)/2][0]+1$。

边界是$f[i][i][0]=f[i][i][1]=1$,答案是$\min\Big\{f[1][n][0],f[1][n][1]\Big\}$

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

template<typename T>
inline void chkmin(T& x,T y) { if (y<x) x=y; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50+10;

char s[N];
int f[N][N][2];

inline int check(int l,int r) {
    if ((r-l+1)%2) return 0;
    int len=r-l+1,mid=(l+r)>>1;
    for (re int i=1;i<=(len>>1);++i)
        if (s[l+i-1]!=s[mid+i]) return 0;
    return 1;
}

int main() {
    scanf("%s",s+1); int n=strlen(s+1);
    memset(f,0x3f,sizeof(f));
    for (re int i=1;i<=n;++i) f[i][i][0]=f[i][i][1]=1;
    for (re int l=2;l<=n;++l)
    for (re int i=1;i+l-1<=n;++i) {
        int j=i+l-1;
        for (re int k=i;k<j;++k) {
            chkmin(f[i][j][0],f[i][k][0]+j-k);
            chkmin(f[i][j][1],min(f[i][k][0],f[i][k][1])+min(f[k+1][j][0],f[k+1][j][1])+1);
        }
        if (check(i,j)) f[i][j][0]=f[i][(i+j)>>1][0]+1;
    }
    printf("%d\n",min(f[1][n][0],f[1][n][1]));
    return 0;
}
最后修改:2019 年 02 月 07 日 08 : 33 PM

2 条评论

  1. smy

    这哪里要区间dp了qwq

    1. M_sea
      @smy

      您强我弱啊

发表评论