[scoi2007]压缩 (洛谷2470)

Posted by yjjr's blog on February 6, 2018

标签:记忆化搜索,DP

题目描述

给一个由小写字母组成的字符串,我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以(但不必)包含大写字母R与M,其中M标记重复串的开始,R重复从上一个M(如果当前位置左边没有M,则从串的开始算起)开始的解压结果(称为缓冲串)。

bcdcdcdcd可以压缩为bMcdRR,下面是解压缩的过程:

已经解压的部分   解压结果    缓冲串

b   b    b

bM   b   

bMc   bc    c

bMcd   bcd    cd

bMcdR   bcdcd    cdcd

bMcdRR   bcdcdcdcd    cdcdcdcd

另一个例子是abcabcdabcabcdxyxyz可以被压缩为abcRdRMxyRz。

输入输出格式

输入格式:

输入仅一行,包含待压缩字符串,仅包含小写字母,长度为n。

输出格式:

输出仅一行,即压缩后字符串的最短长度。

输入输出样例

输入样例#1:

aaaaaaa

输出样例#1:

5

输入样例#2:

bcdcdcdcdxcdcdcdcd

输出样例#2:

12

说明

在第一个例子中,解为aaaRa,在第二个例子中,解为bMcdRRxMcdRR。

【限制】

50%的数据满足:1<=n<=20

100%的数据满足:1<=n<=50

 

分析:

Mark数组用来记忆化存储

每次DP传递的第三个参数t从来记录这段区间内是否存在M

如果t=1,可以分成两段进行压缩,且两段t=1,两段的中间要加一个M,否则前一段会对后一段造成影响

当然也可以只压缩前一段

如果分成等长的两段完全相等且每一段都没放M,可以把后一段换成R

 

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;
int f[maxn][maxn][2];
bool mark[maxn][maxn][2];
char s[maxn];

inline bool same(int a,int b){
    int temp=b-a+1;
    if(temp&1)return 0;
    rep(i,a,(a+b)>>1)
        if(s[i]!=s[i+(temp>>1)])return 0;
    return 1;
}

int dp(int a,int b,bool t)
{
    int temp=b-a+1;
    if(temp==1)return 1;
    if(mark[a][b][t])return f[a][b][t];
    mark[a][b][t]=1;
    if(t)
        rep(i,a,b-1)temp=min(temp,dp(a,i,1)+dp(i+1,b,1)+1);
    rep(i,a,b-1)temp=min(temp,dp(a,i,t)+b-i);
    if(same(a,b))temp=min(temp,dp(a,(a+b)>>1,0)+1);
    return f[a][b][t]=temp;
}

int main()
{
    cin>>s;
    int len=strlen(s);
    cout<<dp(0,len-1,1)<<endl;
    return 0;
}




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