P4302 [SCOI2003]字符串折叠

方杰123 · 2022-10-13 15:16:53 · 个人记录

题目

思路

首先，n\le 100，看到这能想到暴力DP（我在做DP专题当然是DP了）。

设计f[i][j]表示从i到j的折叠后最小长度。然后更新的话很简单，枚举断点。 然后再枚举[i,j]的所有可能的折叠方案（折成几段），更新答案即可。

code

#include<bits/stdc++.h>
using namespace std;
const int N=110;
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 f[N][N],n;
bool check(int l1,int r1,int r2){
    for(int i=r1+1,j=0;i<=r2;i++,j++){
        if(j==r1-l1+1)j=0;
        if(s[i]!=s[l1+j])return false;
    }
    return true;
}
int w(int x){
    if(x<=9)return 1;
    if(x<=99)return 2;
    return 3;
}
int main(){
    cin>>s+1;n=strlen(s+1);
    for(int l=1;l<=n;l++)
        for(int i=1,j=i+l-1;j<=n;i++,j++){f[i][j]=j-i+1;
            for(int k=i;k<j;k++){
                f[i][j]=min(f[i][k]+f[k+1][j],f[i][j]);
                if((j-i+1)%(k-i+1)==0)if(check(i,k,j))
                    f[i][j]=min(f[i][j],f[i][k]+2+w((j-i+1)/(k-i+1)));
            }
        }
    printf("%d",f[1][n]);
    return 0;
}
//NYESYESYES