[SCOI2003]字符串折叠 (区间DP)

时间：2023-03-09 16:30:11
[SCOI2003]字符串折叠 (区间DP)

题目描述

折叠的定义如下：

  1. 一个字符串可以看成它自身的折叠。记作S = S
  2. X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S) = SSSS…S(X个S)。

  3. 如果A = A’, B = B’，则AB = A’B’ 例如，因为3(A) = AAA, 2(B) = BB，所以3(A)C2(B) = AAACBB，而2(3(A)C)2(B) = AAACAAACBB

    给一个字符串，求它的最短折叠。例如AAAAAAAAAABABABCCD的最短折叠为：9(A)3(AB)CCD。

输入输出格式

输入格式：

仅一行，即字符串S，长度保证不超过100。

输出格式：

仅一行，即最短的折叠长度。

输入输出样例

输入样例#1： 
NEERCYESYESYESNEERCYESYESYES
输出样例#1： 
14

说明

一个最短的折叠为：2(NEERC3(YES))

Solution

这道题属于很典型的区间DP.

状态定义:

f[ i ][ j ] 表示从i 到 j 的最小长度.

前导状态:

f [ i ][ j ] 初始化为原长 j - i +1.

f [ i ][ k ] 和 f[ k+1 ][ j ] 枚举断点并且更新.

如果要实现合并操作的话.

我们枚举的两个区间要满足几个条件:

1. 后面 的区间长度要整除前面合并的第一项长度 (因为合并都是从前面开始所以只需考虑后区间被前区间合并)

2. 后面的区间每一段都与其相同.

对于这个,我们直接暴力即可实现.

然后在 hzwer 学长那里学了一个高级的枚举. 无需担心区间边界问题 ! 递归实现 !

代码

#include<bits/stdc++.h>

using namespace std;

char ch[];

int f[][];

bool vich[][];

bool judge(int l,int r,int cl,int cr)

{

         if((r-l+)%(cr-cl+)!=) return ;

         for(int i=l;i<=r;i++)

         if(ch[i]!=ch[(i-l)%(cr-cl+)+cl]) return ;

         return ;

}

int cal(int x)

{int ans=; while(x%!=){ans++;x/=;}return ans;}

//cal 为合并后数字的长度

int ans(int l,int r)

{

    if(vich[l][r])return f[l][r];

    vich[l][r]=;

    f[l][r]=r-l+;

   //初始化为其长度.

    for(int i=l;i<r;i++)

    {

        f[l][r]=min(f[l][r],ans(l,i)+ans(i+,r));

        if(judge(i+,r,l,i))

        f[l][r]=min(f[l][r],ans(l,i)++cal((r-i)/(i-l+)+));

    }

    return f[l][r];

}

int main()

{

    scanf("%s",ch);

    cout<<ans(,strlen(ch)-)<<endl;

}

相关文章