　　题目传送门

字符串折叠

题目描述

折叠的定义如下：

一个字符串可以看成它自身的折叠。记作S = S
X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S) = SSSS…S(X个S)。
如果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：复制

说明

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

　　分析：

　　K_lord的考试里面出的题目。考的时候直接弃疗。。。（先膜一波老余AK%%%）

　　需要用区间DP来做，首先定义动规数组f[l][r]，表示从l到r这一段区间内的字符串折叠后能得到的最短结果。那么枚举折叠的区间，然后枚举左右区间，再枚举可折叠的长度，也就是枚举区间长度的所有因数，然后进行判断该区间是否可以折叠，如果可以则进行状态转移。值得注意的是，转移完以后还需要在进行依次断点枚举，表示将该区间分成两次折叠，看能否得到最短折叠。当然，蒟蒻不擅长动规，还是听了老余讲课，又参考了大佬的博客才弄懂的。如果上面的思路不太懂，就直接看代码吧，代码好懂多了。

　　Code：

#include<bits/stdc++.h>

using namespace std;

char s[];int f[][];

inline bool check(int l,int r,int k)

{

  for(int i=l+k,p=;i<=r;i++,p=(p+)%k)

    if(s[i]!=s[l+p])return false;

  return true;

}

inline int get(int x)

{int ret=;while(x)x/=,ret++;return ret;}

int main()

{

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

  scanf("%s",s+);int n=strlen(s+);

  for(int i=;i<=n;i++)f[i][i]=;

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

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

      int r=l+i-;

      for(int k=;k*k<=i;k++){

    if(i%k==){

      if(check(l,r,i/k))f[l][r]=min(f[l][r],f[l][l+i/k-]+get(k));

      if(check(l,r,k))f[l][r]=min(f[l][r],f[l][l+k-]+get(i/k));}}

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

    f[l][r]=min(f[l][r],f[l][k]+f[k+][r]);}

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

}

巴特西

洛谷P4302 [SCOI]字符串折叠 [字符串，区间DP]

字符串折叠

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章