P4302 [SCOI2003]字符串折叠

Jennie

注意，这个题之所以写成带$()$的形式，不是为了解释说明，而是你最后输出的格式。

然后就是水的一批的区间dp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
template<class T>
void read(T &now){
    now=0;
    char c=getchar();
    int f=1;
    while((!isdigit(c))){
        if(c=='-') f=-1;
    //  cout<<isdigit(c)<<" "<<c<<" ";
        c=getchar();
    }
    while(isdigit(c)){
        now=(now<<1)+(now<<3)+c-'0';
        c=getchar();
    }
    now*=f;
}
string s;
int f[1001][1001];
int l;
bool check(int ll,int r,int kk){
    int tem=(r-ll+1)/kk;
    for(int i=0;i<kk;++i){
        for(int j=1;j<tem;++j){
            if(s[ll+(j*kk)+i]!=s[ll+((j-1)*kk)+i]){
                return 0;
            }
        }
    }
    return 1;
}
int main(){
    cin>>s;
    l=s.length();
    s=' '+s;
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=l;++i){
        f[i][i]=1;
    }
    for(int ll=2;ll<=l;++ll){
        for(int i=1;i+ll-1<=l;++i){
            int r=i+ll-1;
            for(int k=i;k<r;++k){
                f[i][r]=min(f[i][k]+f[k+1][r],f[i][r]);
            }
            for(int k=1;k<=ll/2;++k){
                if(ll%k!=0) continue;
                if(check(i,r,k)){
                    f[i][r]=min(f[i][r],f[i][i+k-1]+2+(ll/k==100?3:(ll/k>=10?2:1)));
                }
            }
        }
    }
    cout<<f[1][l];
    return 0;
}