题目描述
折叠的定义如下:
- 一个字符串可以看成它自身的折叠。记作S = S
- X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S) = SSSS…S(X个S)。
-
如果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; }