P4302 [SCOI2003]字符串折叠

题目描述

折叠的定义如下:

  1. 一个字符串可以看成它自身的折叠。记作S = S
  2. X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S) = SSSS…S(X个S)。
  3. 如果A = A’, B = B’,则AB = A’B’ 例如,因为3(A) = AAA, 2(B) = BB,所以3(A)C2(B) = AAACBB,而2(3(A)C)2(B) = AAACAAACBB

    给一个字符串,求它的最短折叠。例如AAAAAAAAAABABABCCD的最短折叠为:9(A)3(AB)CCD。

输入输出格式

输入格式:

仅一行,即字符串S,长度保证不超过100。

输出格式:

仅一行,即最短的折叠长度。

输入输出样例

输入样例#1: 复制
NEERCYESYESYESNEERCYESYESYES
输出样例#1: 复制
14

说明

一个最短的折叠为:2(NEERC3(YES))

区间dp,转移时只有右区间能用若干个左区间表示出来时才转移

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e2+10;

char a[maxn];

int f[maxn][maxn],n;

bool get(int x,int y,int x1,int y1) {
    if((y1-x+1)%(y-x+1)!=0) return false;
    int len=y-x+1;
    for(int i=x1;i<=y1;i++) {
        if(a[i]!=a[i-len]) return false;
    }
    return true;
}

int cal(int k ){
    int sum=0;
    while(k) {
        sum++;
        k/=10;
    }
    return sum;
}

int main() {
    scanf("%s",&a);
    memset(f,0x3f,sizeof(f));
    n=strlen(a);
    for(int i=0;i<n;i++) f[i][i]=1;
    for(int l=1;l<n;l++) 
        for(int i=0;i+l<n;i++) {
            int j=i+l;
            f[i][j]=j-i+1;
            for(int k=i;k<j;k++) {
                if(!get(i,k,k+1,j)) 
                   f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);      
                else f[i][j]=min(f[i][j],f[i][k]+2+cal((l+1)/(k-i+1)));           
            }
        }
    printf("%d",f[0][n-1]);
    return 0;
}

 

上一篇:1530 好叶子节点对的数量


下一篇:跪求!阿里P9手写的这份1530页的Java核心编程技术手册