题解洛谷P4302 【[SCOI2003]字符串折叠】

一眼区间\(dp\)，但蒟蒻的我还是调了好久\(qwq\)

【状态设置】

设\(f[i][j]\)为子串\([i,j]\)的最短折叠

目标为\(f[1][n]\)

【初始化】

\(1\) 首先对于任意的\(i\)必然存在\(f[i][i]=1\)

然后其他的都初始化为\(INF\)即可

\(2\) 因为最后的字符串可能会出现数字，所以不妨考虑用一个数组\(g[x]\)预处理\(x\)的位数\(qwq\)

【\(dp\)核心】

对于任意的\(f[i][j]\) \((i < j)\)可以有两种得到方式。

分成两段，两段的最短折叠连在一起构成，即左区间\(+\)右区间
自身构成：找子串\([i,j]\)中的一个循环子串，形如 循环节左括号子串右括号。长度即为即循环节位数\(+2+\)子串长度。

第一种方式，套区间\(dp\)的模板，先枚举出\(len\)和\(i\)，得到\(j=i+len-1\)，再跑一遍\(k\)枚举割点，于是得到：

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

\[i \leq k < j
\]

第二种方式，如果子串\([i,k]\)是子串\([i,j]\)中的一个循环子串，则：

\[f[i][j]=min(f[i][j],g[len/l]+2+f[i][k])
\]

\[l=k-i+1
\]

【代码】

#include<bits/stdc++.h>

using namespace std;

const int max_n=100+5;

int n,g[max_n],f[max_n][max_n];

string st;

bool check(int ll,int rr,int len){//判断是否是循环节

	for(int i=ll;i<=ll+len-1;i++){

		char ch=st[i];

		for(int j=i;j<=rr;j+=len){

			if(st[j]!=ch)return false;

		}

	}

	return true;

}

int main(){

    ios::sync_with_stdio(false);

    cin>>st;

    n=st.size();st=" "+st;//把字符串变成1~n

    for(int i=1;i<=9;i++)g[i]=1;

    for(int i=10;i<=99;i++)g[i]=2;

	g[100]=3;//g[x]表示x的位数

    memset(f,0x3f,sizeof(f));

    for(int i=1;i<=n;i++)f[i][i]=1;//初始化f数组

    for(int len=1;len<=n;len++){

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

    		int j=i+len-1;//区间DP模板，得到i和j

    		for(int k=i;k<j;k++){//枚举哪里切

    		    f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);//第一种情况，左区间+右区间

    		    int l=k-i+1;//第二种情况，先得到循环节的长度

    		    if(len%l)continue;//长度不符

    		    if(check(i,j,l))f[i][j]=min(f[i][j],g[len/l]+2+f[i][k]);//是循环节，那么套公式

			}

		}

	}

	cout<<f[1][n]<<"\n";

	return 0;

}

\(\operatorname{Update}\) \(\operatorname{On}\) \(\operatorname{2019.08.28}\)

巴特西

题解洛谷P4302 【[SCOI2003]字符串折叠】

最新文章

热门文章

巴特西

题解 洛谷P4302 【[SCOI2003]字符串折叠】

最新文章

热门文章

题解洛谷P4302 【[SCOI2003]字符串折叠】