1090. [SCOI2003]字符串折叠【区间DP】

亦凉 2022-10-03 00:48 109阅读 0赞

## Description ##

折叠的定义如下： 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。

## Input ##

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

## Output ##

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

## Sample Input ##

NEERCYESYESYESNEERCYESYESYES

## Sample Output ##

## HINT ##

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

dp\[i\]\[j\]表示区间\[i,j\]的最短折叠长度  
除了常规判断将区间划分成\[i,k\]\[k+1,j\]两个区间判断外  
还要将两个区间check一下，枚举len,看这两个区间能否都压成长度为len的字符串  
能的话就再更新一下答案即可

1 #include<iostream>
     2 #include<cstring>
     3 #include<cstdio>
     4 using namespace std;
     5 char a[150];
     6 int dp[150][150],n;
     7 int check(int x1,int y1,int x2,int y2)
     8 {
     9     int len1=y1-x1+1,len2=y2-x2+1;
    10     int minn=min(len1,len2);
    11     int ans=0x7fffffff;
    12     for (int i=1;i<=minn;++i)
    13     {
    14         bool flag=true;
    15         if (len1%i!=0 || len2%i!=0) continue;
    16         
    17         for (int j=0;j<len1;++j)
    18             if (a[x1+j]!=a[x2+j%i])
    19                 flag=false;
    20         for (int j=0;j<len2;++j)
    21             if (a[x2+j]!=a[x1+j%i])
    22                 flag=false;
    23         if (flag)
    24             ans=min(ans,3+dp[x1][y1]+((len2+len1)/i>=10));
    25     }
    26     return ans;
    27 }
    28 
    29 int main()
    30 {
    31     scanf("%s",&a);
    32     n=strlen(a);
    33     memset(dp,0x3f,sizeof(dp));
    34     for (int i=0;i<n;++i) dp[i][i]=1;
    35     for (int i=2;i<=n;++i)
    36     {
    37         for (int j=0;j<n-i+1;++j)
    38         {
    39             int x=j,y=j+i-1;
    40             for (int k=x;k<y;++k) 
    41             {
    42                 dp[x][y]=min(dp[x][y],dp[x][k]+dp[k+1][y]);
    43                 dp[x][y]=min(dp[x][y],check(x,k,k+1,y));
    44             }
    45              
    46         }
    47     }
    48     printf("%d",dp[0][n-1]);
    49 }

转载于:https://www.cnblogs.com/refun/p/8680797.html