这道题目可以说是一道非常好非常一颗赛艇的DP题了。
需要注意的是，其中情形3)，字符串必然能完全转化为 N(str)形式，如果有N(str1)M(str2)等等另外样式，应该首先使用拼接形式对其进行划分。
那么，我们首先考虑写一个用来压缩情形3)下的字符串的函数zip()：
char str[];
int bit(int n)
{
int cnt=;
while(n>)
{
n/=;
cnt++;
}
return cnt;
}
int zip(int l,int r)
{
int len=r-l+;
bool flag;
if(len<=) return len;
for(int sec=;sec<len;sec++)//循环节长度
{
if(len%sec) continue;//不能完全转化为N(str)形式
flag=;
for(int p=;p<=sec;p++)//遍历循环节中的每个结点
{
char now=str[l+p-];
for(int i=l+sec;i<=r;i+=sec)//遍历每个循环节的头结点
{
if(str[i+p-]!=now)
{
flag=;
break;
}
}
if(!flag) break;
}
if(flag) return(bit(len/sec) + + sec);//如果字符串可以按这个循环节进行压缩
}
return len;
}
使用比较暴力的方法，并不难写，bit()函数返回一个数字是几位数。
既然有了zip()函数，那么就可以进一步考虑状态转移方程了，如下:
dp[i][j] = min( j - i + 1 , dp[i][k] + dp[k+1][j] , zip( i , j ) ); （即情形1) 2) 3)中选取最小的）
其中,dp[i][j]表示字符串str[i,j]的压缩后最短长度。
最后，我们考虑如何进行状态转移，联想到之前http://www.cnblogs.com/dilthey/p/6889141.html中的归并思路，
我们也可以对本题进行一定的归并，首先初始化所有dp[i][i]=1，然后，依次计算出j - i = 1,2,3,……,n-1的dp[i][j]，
另外要注意的是，我们要对zip()函数做一点小修改，如果不修改的话，样例都过不了嗷
#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
char str[];
int dp[][];
int bit(int n)
{
int cnt=;
while(n>)
{
n/=;
cnt++;
}
return cnt;
}
int zip(int l,int r)
{
int len=r-l+;
bool flag;
if(len<=) return len;
for(int sec=;sec<len;sec++)//循环节长度
{
if(len%sec) continue;//不能完全转化为N(str)形式
flag=;
for(int p=;p<=sec;p++)//遍历循环节中的每个结点
{
char now=str[l+p-];
for(int i=l+sec;i<=r;i+=sec)//遍历每个循环节的头结点
{
if(str[i+p-]!=now)
{
flag=;
break;
}
}
if(!flag) break;
}
if(flag) return(bit(len/sec) + + dp[l][l+sec-]);//如果字符串可以按这个循环节进行压缩
}
return len;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%s",str+);
int len=strlen(str+);
for(int i=;i<=len;i++) dp[i][i]=;
for(int l=;l<=len;l++)
{
for(int i=,j=i+l-;j<=len;i++,j=i+l-)
{
int tmp=INF;
for(int k=i;k<j;k++) if(tmp>dp[i][k]+dp[k+][j]) tmp=dp[i][k]+dp[k+][j];
dp[i][j]=min( min(l,tmp) ,zip(i,j) );
}
}
printf("%d\n",dp[][len]);
}
}
当然，这不是一种很优化的算法，时间复杂度大概在O(len^3)，可以考虑进行一定的优化。不过反正我是想不出