Description
折叠的定义如下： 1. 一个字符串可以看成它自身的折叠。记作S S 2. X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S) SSSS…S(X个S)。 3. 如果A A’, BB’，则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。
Input
仅一行，即字符串S，长度保证不超过100。
Output
仅一行，即最短的折叠长度。
Sample Input
NEERCYESYESYESNEERCYESYESYES
Sample Output
14
HINT
一个最短的折叠为：2(NEERC3(YES))
没想到居然是dp,区间dp
定义dp[i][j]表示字符串[i,j]最小折叠长度,有两种状态转移的形式,如果l到r这个区间里面不能折叠,那就只能枚举中间点,由左右两部分可折叠长度相加的转移而来
f ( l , r ) = m i n ( f ( l , r ) , f ( l , i ) + f ( i + 1 , r ) ) f(l,r)=min(f(l,r),f(l,i)+f(i+1,r)) f(l,r)=min(f(l,r),f(l,i)+f(i+1,r))
而如果本身这个区间就可以折叠的,那假设右边部分可以由左边部分重复而来,那么就是
f ( l , r ) = m i n ( f ( l , r ) , f ( l , i ) + 2 + c a l ( ( r − i ) / ( i − l + 1 ) + 1 ) ) f(l,r)=min(f(l,r),f(l,i)+2+cal((r-i)/(i-l+1)+1)) f(l,r)=min(f(l,r),f(l,i)+2+cal((r−i)/(i−l+1)+1))
这个f(l,i)就是左边部分的长度,折叠后就以这个来表示,2就是括号长度,后面的cal就是计算整个l,r区间由多少个左部分组成,就是这个数字的长度,比如14,长度就是2
代码:
#include <bits/stdc++.h>
using namespace std;
const int N=105;
char s[N];
//dp[i][j]表示[i,j]最小折叠长度
int dp[N][N];
int cal(int x){
int t=0;
while(x){
t++;
x/=10;
}
return t;
}
//判断[l,r]能否由[cl,cr]重复而成
bool judge(int l,int r,int cl,int cr){
//长度不能整除
if((r-l+1)%(cr-cl+1)!=0){
return false;
}
//枚举右部分每一个字符
for(int i=l;i<=r;i++){
//按顺序判断,注意取模
//右边部分可能有多个左边部分
if(s[i]!=s[(i-l)%(cr-cl+1)+cl]){
return false;
}
}
return true;
}
int solve(int l,int r){
if(l==r){
return 1;
}
if(dp[l][r]){
return dp[l][r];
}
int t=r-l+1;
//枚举断点
for(int i=l;i<r;i++){
t=min(t,solve(l,i)+solve(i+1,r));
if(judge(i+1,r,l,i)){
//+solve(l,i)折叠后那部分的长度
//+2两个括号
//+get()折叠后数字的长度
t=min(t,solve(l,i)+2+cal((r-i)/(i-l+1)+1));
}
}
return dp[l][r]=t;
}
int main(void){
scanf("%s",s);
int len=strlen(s);
printf("%d\n",solve(0,len-1));
return 0;
}
京公网安备 11010502036488号