【BZOJ 1090】 [SCOI2003]字符串折叠

1090: [SCOI2003]字符串折叠Time Limit:10 SecMemory Limit:162 MBSubmit:637Solved:419[Submit][Status]Description

折叠的定义如下： 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。

Input

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

Output

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

Sample Input

NEERCYESYESYESNEERCYESYESYES

Sample Output

14

HINT

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

区间dp水题。

f[i][j]表示把i-j这一段压缩的最短长度，那么f[i][j]=min(f[i][j],f[i][k]+f[k+1][j],写成k(str))

#include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <string>using namespace std;char s[105];int f[105][105];bool ok(int l,int r,int x){int st=l;while (1){if (st+x>r) break;int p=st+x;for (int i=0;i<x;i++)if (s[st+i]!=s[p+i]) return 0;st=p;}return 1;}int calc(int x){int ans=0;while (x){ans++;x/=10;}return ans;}int dp(int l,int r){if (l==r) return f[l][r]=1;if (f[l][r]>0) return f[l][r];int now=r-l+1;f[l][r]=now;for (int i=1;i<=now/2;i++)if (now%i==0&&ok(l,r,i))f[l][r]=min(f[l][r],2+calc(now/i)+dp(l,l+i-1));for (int i=l;i<r;i++)f[l][r]=min(f[l][r],dp(l,i)+dp(i+1,r));return f[l][r];}int main(){scanf("%s",s+1);int l=strlen(s+1);memset(f,-1,sizeof(f));cout<<dp(1,l);return 0;}

感悟：

写这题一定要注意，转化成k(str)之后，k可能不只占一位。。。。

旅行还在继续，这个过程是艰难而又孤单的。