bzoj 1090: [SCOI2003]字符串折叠【区间dp】

设f[i][j]为区间(i,j)的最短长度，然后转移的话一个是f[i][j]=min(j-i+1,f[i][k]+f[k+1][j])，还有就是把(k+1,j)合并到(i,k)上，需要判断一下字符串相同，然后转移的时候注意字符串计数的那个数字也是按位数算的，要计算一下位数

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=105;

int n,f[N][N];

char s[N];

bool ok(int l1,int r1,int l2,int r2)

{

	if((r1-l1+1)%(r2-l2+1)!=0)

		return 0;

	for(int i=l1;i<=r1;i++)

		if(s[i]!=s[(i-l1)%(r2-l2+1)+l2])

			return 0;

	return 1;

}

int clc(int x)

{

	int r=0;

	while(x)

		r++,x/=10;

	return r;

}

int main()

{

	scanf("%s",s+1);

	n=strlen(s+1);

	for(int i=1;i<=n;i++)

		f[i][i]=1;

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

		for(int i=1;i+l-1<=n;i++)

		{

			int j=i+l-1;

			f[i][j]=l;

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

			{

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

				if(ok(k+1,j,i,k))

					f[i][j]=min(f[i][j],f[i][k]+2+clc((j-k)/(k-i+1)+1));

			}

		}

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

	return 0;

}

巴特西

bzoj 1090: [SCOI2003]字符串折叠【区间dp】

最新文章

热门文章