[SCOI2003]字符串折叠

Time Limit:10000MS  Memory Limit:165536K
Total Submit:21 Accepted:15
Case Time Limit:1000MS

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))

Source
晕。。SCOI这种类型的题目怎么这么多囧。。这道题差不多吧，也是Dp，比压缩还简单，就不说了。。
另外<?=这个操作符很NB。。
Code：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxl=120;
char M[maxl];
bool S[maxl][maxl]={0};
int Dp[maxl][maxl];
bool Match(int p,int Len,int s)
{
if(Len%s)return false;
rep(i,Len) if(M[p+i]!=M[p+i%s]) return false;
return true;
}
int Cost(int x)
{
if(x<10) return 1;
return 1+Cost(x/10);
}
int dfs(int l,int r)
{
int&x=Dp[l][r];if(S[l][r]) return x;
S[l][r]=true;int Len=r-l+1;x=Len;if(Len==1) return x;
for(int k=l;k<r;k++)x<?=dfs(l,k)+dfs(k+1,r);
for(int k=1;k<Len;k++)if(Match(l,Len,k))x<?=dfs(l,l+k-1)+2+Cost(Len/k);
return x;
}
int main()
{
//freopen("in","r",stdin);
cin>>M;
cout<<dfs(0,strlen(M)-1)<<endl;
}