P2470 [SCOI2007]压缩

方杰123 · 2022-10-15 14:32:24 · 个人记录

题目

思路

开始以为是与这题一样，打完以后开始意识到事情不对劲。这题的压缩规则比较特殊：

1. 把两段重复的字符串进行合并，但是每段中间不能已经压缩过（这回导致多了一个M），但是每段的开头又是可以压缩的。
2. 压缩的的头为1时答案减一。

在经历一个小时的挣扎（修改）后，成功列出一下恶心的方程式：

f[i][j][k]:表示区间为[i,j]种类为k的最短长度
f[i][j][0]:不进行任何压缩，f[i][j][0]=j-i+1;(其实这个状态没必要)
f[i][j][1]:整个区间被压形成的字符串最短长度。
f[i][j][2]:头部压缩，后面没压缩的最短长度
f[i][j][3]:随便组合（包括前面所有情况）

具体看注释。

code

#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0,f=1;char c=getchar();
    while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
char s[110];
int n,f[110][110][4];//0表示无压缩，1全压缩，2头压缩剩下不压缩，3任意组合！！！！！！！！！ 
bool check(int i,int j){
    int l=(j-i+1)/2;
    for(int k=i;k<=i+l-1;k++)
        if(s[k]!=s[k+l])return false;
    return true;
}
int main(){
    cin>>s+1;n=strlen(s+1);for(int i=1;i<=n;i++)f[i][i][1]=0x3f3f3f3f,f[i][i][0]=1,f[i][i][2]=0x3f3f3f3f,f[i][i][3]=1;
    for(int l=2;l<=n;l++){
        for(int i=1,j=i+l-1;j<=n;i++,j++){
            f[i][j][3]=f[i][j][0]=l; f[i][j][1]=0x3f3f3f3f;f[i][j][2]=0x3f3f3f3f;//初始值
            for(int k=i;k<j;k++)f[i][j][3]=min(f[i][j][3],f[i][k][3]+f[k+1][j][3]);//任意组合
            for(int k=i;k<j;k++)f[i][j][2]=min(f[i][j][2],min(f[i][k][2],f[i][k][1])+f[k+1][j][0]);//压缩头+不压缩尾
            f[i][j][3]=min(f[i][j][3],f[i][j][2]);
            if(l%2==0){
                int k=i+l/2-1;
                if(check(i,j)){
                    f[i][j][1]=min(f[i][k][0]+1+(i!=1),min(f[i][k][2],f[i][k][1])+1);//压缩（不压缩，头压缩尾巴不压缩）（别忘了1为头减一）
                    f[i][j][3]=min(f[i][j][3],f[i][j][1]);
                }
            }
        }
    }
    printf("%d",f[1][n][3]);
    return 0;
}