「BZOJ1090」[SCOI2003] 字符串折叠

2014年3月9日5,6910

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[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];

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[101];
int f[101][101];
bool mark[101][101];
bool jud(int l,int r,int cl,int cr)
{
     if((r-l+1)%(cr-cl+1)!=0)return 0;
     for(int i=l;i<=r;i++)
        if(s[i]!=s[(i-l)%(cr-cl+1)+cl])return 0;
     return 1;
 }
int get(int x)
{int t=0;while(x){x/=10;t++;}return t;}
int dp(int l,int r)
{
    if(l==r)return 1;
    if(mark[l][r])return f[l][r]; 
    mark[l][r]=1;
    int t=r-l+1;
    for(int i=l;i<r;i++)
    {
            t=min(t,dp(l,i)+dp(i+1,r));
            if(jud(i+1,r,l,i))
            t=min(t,dp(l,i)+2+get((r-i)/(i-l+1)+1)); 
            }
    return f[l][r]=t;
    } 
int main()
{
    scanf("%s",s);
    printf("%d",dp(0,strlen(s)-1));
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

char s[101];

int f[101][101];

bool mark[101][101];

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

{

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

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

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

return 1;

}

int get(int x)

{int t=0;while(x){x/=10;t++;}return t;}

int dp(int l,int r)

{

if(l==r)return 1;

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

mark[l][r]=1;

int t=r-l+1;

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

{

t=min(t,dp(l,i)+dp(i+1,r));

if(jud(i+1,r,l,i))

t=min(t,dp(l,i)+2+get((r-i)/(i-l+1)+1));

}

return f[l][r]=t;

}

int main()

{

scanf("%s",s);

printf("%d",dp(0,strlen(s)-1));

return 0;

}

« 「BZOJ1068」[SCOI2007] 压缩「BZOJ1260」[CQOI2007] 涂色paint »

hzwer.com _ Home | http://hzwer.com

「BZOJ1090」[SCOI2003] 字符串折叠

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论