BZOJ1090 [SCOI2003]字符串折叠 区间动态规划 字符串

时间：2023-03-08 16:34:32

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解

题目传送门 - BZOJ1090

题意概括

　　折叠的定义如下：

　　　　1. 一个字符串可以看成它自身的折叠。记作S

　　　　2. X(S)是X(X>1)个S连接在一起的串的折叠。

　　n<=100.让你求折叠之后的最小长度。

题解

　　（据说字符串的题有通用做法？——hash+乱搞？？）

　　首先预处理出从第i个位置开始的连续j个字符最多重复了几次。

　　可以用哈希，但是数据范围小，直接暴力匹配就可以了。

　　然后，区间动归，记忆化dfs，dp[i][j]表示i~j这一段最少可以折叠成多少。

　　具体的状态转移见代码的dfs段。

代码

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <cstdio>

#include <cmath>

using namespace std;

const int N=+;

const int Inf=;

char str[N];

int n;

int dp[N][N],match[N][N];

int num_digit(int x){

    int ans=;

    while (x)

        ans++,x/=;

    return ans;

}

int dfs(int L,int R){

    if (L>R)

        return ;

    if (dp[L][R]!=-)

        return dp[L][R];

    dp[L][R]=dfs(L+,R)+;

    for (int i=;L+i-<=R;i++)

        for (int j=;j<=match[L][i]&&L+i*j<=R+;j++)

            dp[L][R]=min(dp[L][R],dfs(L,L+i-)+num_digit(j)++dfs(L+i*j,R));

    return dp[L][R];

}

int main(){

    scanf("%s",str+);

    n=strlen(str+);

    for (int i=;i<=n;i++)//枚举位置

        for (int j=;i+j-<=n;j++){//枚举长度

            match[i][j]=;

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

                if ((k-i)%j==)

                    match[i][j]++;

                if (str[k]!=str[k-j])

                    break;

            }

        }

    memset(dp,-,sizeof dp);

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

        dp[i][i]=;

    printf("%d",dfs(,n));

    return ;

}

相关文章