Bzoj1090 [scoi2003]字符串折叠

Posted by yjjr's blog on February 6, 2018

标签:区间DP

Description

 S 2. X(S)是X(Xà折叠的定义如下: 1. 一个字符串可以看成它自身的折叠。记作S>AAACAAACBB 给一个字符串,求它的最短折叠。例如AAAAAAAAAABABABCCD的最短折叠为:9(A)3(AB)CCD。àAAACBB,而2(3(A)C)2(B)à A’B’ 例如,因为3(A) = AAA, 2(B) = BB,所以3(A)C2(B) àB’,则AB àA’, Bà SSSS…S(X个S)。 3. 如果A à1)个S连接在一起的串的折叠。记作X(S)

Input

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

Output

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

Sample Input

NEERCYESYESYESNEERCYESYESYES

Sample Output

14

HINT

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

和SCOI07 压缩很相似

记忆化搜索,dp(l,r)表示làr的最短长度

经典的区间DP方程dp(l,r)=min{dp(l,i)+dp(i+1,r)}l<=i<r

但是要考虑到该子串内部是否可以合并的问题

用ablej判断从lài与i+1àr是否可以合并,用calc计算合并后十进制数字的位数

 

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
const int maxn=106,inf=0x3f3f3f;
char s[maxn];
bool mark[maxn][maxn];
int f[maxn][maxn],len;
 
inline int calc(int x){int y=0;while(x){x/=10;y++;}return y;}
 
bool ablej(int l,int r,int L,int R){
    if(((R-L+1)%(r-l+1))!=0)return 0;
    rep(i,L,R)
        if(s[i]!=s[l+((i-L)%(r-l+1))])return 0;
    return 1;
}
 
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;
    rep(i,l,r-1){
        t=min(t,dp(l,i)+dp(i+1,r));
        if(ablej(l,i,i+1,r))t=min(t,dp(l,i)+2+calc(((r-i)/(i-l+1))+1));
    }
    return f[l][r]=t;
}
 
int main()
{
    scanf("%s",s);
    len=strlen(s);
    printf("%d\n",dp(0,len-1));
    return 0;
}



本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr