【BZOJ1090】[SCOI2003]字符串折叠（动态规划）

题面

BZOJ

洛谷

题解

区间\(dp\)。设\(f[i][j]\)表示压缩\([i,j]\)区间的最小长度。显然可以枚举端点转移。再考虑这一段区间能否压缩，暴力枚举一个压缩后的串长，判断是否全部相等即可。判相等不如用哈希，方便得多。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define ull unsigned long long

#define MAX 150

const int base=233;

ull hs[MAX],pw[MAX];

ull get(int l,int r){return hs[r]-hs[l-1]*pw[r-l+1];}

int n,f[MAX][MAX];

char s[MAX];

int ws(int x){int s=0;while(x)++s,x/=10;return s;}

int main()

{

	scanf("%s",s+1);n=strlen(s+1);pw[0]=1;

	for(int i=1;i<=n;++i)hs[i]=hs[i-1]*base+s[i];

	for(int i=1;i<=n;++i)pw[i]=pw[i-1]*base;

	memset(f,63,sizeof(f));

	for(int i=1;i<=n;++i)f[i][i]=1;

	for(int len=2;len<=n;++len)

		for(int i=1,j=len;j<=n;++i,++j)

		{

			for(int k=i;k<j;++k)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);

			for(int k=1;k<=len;++k)

				if(len%k==0)

				{

					bool fl=true;

					for(int l=i;l<=j;l+=k)

						if(get(i,i+k-1)!=get(l,l+k-1))

							fl=false;

					if(fl)f[i][j]=min(f[i][j],ws(len/k)+2+f[i][i+k-1]);

				}

		}

	printf("%d\n",f[1][n]);

	return 0;

}