1090: [SCOI2003]字符串折叠
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
题解详见 Hzwer学长博客
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define MaxN 101
char s[MaxN];
int len,f[MaxN][MaxN];
bool check(int l,int r,int x,int y){
int s1=(r-l+1);
int s2=(y-x+1);
if (s1%s2) return false;
int j=x;
for (int i=l;i<=r;++i){
if (s[i]!=s[j]) return false;
++j;
if (j>y) j=x;
}
return true;
}
int get(int x){
int s=0;
for (;x;x/=10,++s);
return s;
}
int calc(int l,int r){
if (l==r) return 1;
if (f[l][r]) return f[l][r];
int ans=r-l+1;
for (int i=l;i<r;++i){
ans=min(ans,calc(l,i)+calc(i+1,r));
if (check(l,i,i+1,r))
ans=min(ans,calc(i+1,r)+2+get((i-l+1)/(r-i)+1));
}
f[l][r]=ans;
return f[l][r];
}
int main(){
scanf("%s",s+1);
len=strlen(s+1);
printf("%d\n",calc(1,len));
}
评论 (0)
