即字符串S,即最短的折叠长度澳门娱乐6165:

作者:澳门娱乐

澳门娱乐6165,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。

2014年3月9日3,1140

Input

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

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。

Output

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

Input

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

Sample Input

NEERCYESYESYESNEERCYESYESYES

Output

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

Sample Output

14

Sample Input

NEERCYESYESYESNEERCYESYESYES

HINT

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

Sample Output

14

Source

HINT

 

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

 

题解

容易看出来是区间dp...

转移方程$f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]$

但是怎么处理字符串的折叠这一块很懵逼

首先一个字符串能够折叠成它的一个字串,要满足的一个很显然的条件是能够被这个子串整除,那么就可以减少掉很多无用状态的枚举了

然后对于能够整除的情况,一个一个向后暴力匹配,时间复杂度还是过得去的毕竟n那么小

注意在匹配的过程中如果有一位不相同就可以直接跳掉了

转移方程$f[l][r]=min(f[l][r],f[l][l+k-1]+2+idx((r-l+1)/k)$

$idx$是用来判断前面的数字的长度的,如果小于10返回1小于100返回2小于1000返回3

初始化就是$f[l][r]=r-l+1$但是这里会没有覆盖到单个字母的情况,所以还要再初始化一下$f[i][i]=1$

#include <bits/stdc++.h>
using namespace std;
char ch[200];
int n;
int f[200][200];
int idx(int x){
    if(x<10)return 1;
    if(x<100)return 2;
    return 3;
}
bool check(int l,int r,int len){
    for(int i=1;i<=len;i++){
        for(int j=l+i-1;j+len<=r;j+=len){
            if(ch[j]!=ch[j+len])return 0;
        }
    }
    return 1;
}
int main(){
    scanf("%s",ch+1);
    n=strlen(ch+1);
    for(int l=n;l;l--){
        f[l][l]=1;
        for(int r=l+1;r<=n;r++){
            f[l][r]=r-l+1;
            for(int k=l;k<=r;k++){
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]);
            }
            for(int k=1;k<=r-l+1;k++){
                if((r-l+1)%k==0&&check(l,r,k)){
                    f[l][r]=min(f[l][r],f[l][l+k-1]+idx((r-l+1)/k)+2);
                }
            }
        }
    }
    printf("%dn",f[1][n]);
    return 0;
}

 

题解

dp[l][r]表示l~r的最短折叠长度

即可推出:dp[l][r]=min(r-l+1,dp[l][k]+dp[k+1][r])l<=k<r

当k+1~r可以由l~k重复得到时还要:dp[l][r]=min(dp[l][r],dp[l][k]+2+calc((r-l+1)/(k-l+1)));//calc用来计算一个十进制数所占位数

答案就是dp[0][len-1];

 

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstdlib>
 6 #include<cstring>
 7 #define N 107
 8 using namespace std;
 9 
10 int len;
11 int f[N][N],mark[N][N];
12 char s[N];
13 
14 bool judge(int l,int r,int hl,int hr)
15 {
16     int mod=(r-l)+1;
17     if ((hr-hl+1)%(r-l+1)!=0) return false;
18     for (int i=0;i<hr-hl+1;i++)
19         if (s[l+i%mod]!=s[hl+i]) return false;
20     return true;    
21 }
22 int wei(int x)
23 {
24     int zhi=0;
25     while (x)
26     {
27         zhi++;
28         x/=10;
29     }
30     return zhi;
31 }
32 int dfs(int l,int r)
33 {
34     if (l==r) return 1;
35     if (mark[l][r]) return f[l][r];
36     mark[l][r]=1;
37     int res=r-l+1;
38     for (int i=l;i<r;i++)
39     {
40         res=min(res,dfs(l,i)+dfs(i+1,r));
41         if (judge(l,i,i+1,r)) res=min(res,dfs(l,i)+2+wei((r-i)/(i-l+1)+1));
42     }
43     return f[l][r]=res;
44 }
45 int main()
46 {
47     scanf("%s",s);
48     len=strlen(s);
49     printf("%dn",dfs(0,len-1));
50 }

 

 

本文由澳门娱乐6165发布,转载请注明来源

关键词: