[SCOI2007]压缩(动态规划,区间dp,字符串哈希)

[SCOI2007]压缩

状态:设\(dp[i][j]\)表示前i个字符,最后一个\(M\)放置在\(j\)位置之后的最短字串长度.

转移有三类,用刷表法来实现.

第一种是直接往压缩串后面填字符,这样就是:

\[dp[i+1][j]=min(dp[i+1][j],dp[i][j]+1)
\]

另外一种就是往字串里添加\(R\),要满足相邻两个字符串是匹配的,可以用字符串哈希来快速匹,另外下面的\(k\)和\(sz\)要倍增往后跳(因为重复的串长在成倍增加,题目的样例解释的很清楚了).

\[dp[k][j]=min(dp[k][j],dp[k-sz][j]+1)
\]

当然还要往后填\(M\)

\[dp[i][i]=min(dp[i][i],dp[i][j])
\]

时间复杂度\(O(n^2logn)\)

代码很好懂.

#include<bits/stdc++.h>

#define ull unsigned long long

#define maxn 55

using namespace std;

const int base=233;

ull ha[maxn],pw[maxn];

char s[maxn];

int n,ans,dp[maxn][maxn];

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

int main()

{

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

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

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

	memset(dp,0x3f,sizeof(dp));dp[1][0]=1;

	//dp[i][j]表示前i个字符,上一个M放在j位置之后的最短加密字串

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

	{

		for(int j=0;j<i;j++)dp[i][i]=min(dp[i][i],dp[i][j]+1);

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

		{

			dp[i+1][j]=min(dp[i+1][j],dp[i][j]+1);//往后直接添加字母

			if(i==j)continue;

			int sz=i-j;ull haha=gethash(j+1,i);

			for(int k=i+sz;k<=n;k+=sz)//倍增加R

			{

				if(haha==gethash(k-sz+1,k))//哈希匹配字符串

					dp[k][j]=min(dp[k][j],dp[k-sz][j]+1);

				else break;

				haha=haha*pw[sz]+haha;sz<<=1;

			}

		}

	}

	ans=1e9;

	for(int j=0;j<n;j++)ans=min(ans,dp[n][j]);

	cout<<ans<<endl;

	return 0;

}

巴特西

[SCOI2007]压缩(动态规划,区间dp,字符串哈希)

[SCOI2007]压缩

最新文章

热门文章