值得记录的每日一题

Posted on | In

7.13 区间dp

https://ac.nowcoder.com/acm/problem/20252

字符串最长50，求压缩后的最短长度。

这题的关键在于M。如果只有R，那么就是基础的区间dp，每次可以压缩时令dp(l,r) = min(dp(l,r), dp(l,mid)+1)，三重循环搞定。多出了规定“M”改变了什么呢？首先是每组压缩前要多一个字母，其次，如果[l, mid]中有M，那么它是不可以和[mid+1,r]合并的，这是因为题设中末尾的R会优先匹配距离它近的M，而不是l之前的M。

所以我们每处dp要记录两个值，令dp[l][r][0]表示[l, r]中不出现M的情况下，最短的压缩长度；dp[l][r][1]则表示允许出现M时的最短长度。这样一来当我们执行压缩时用的是dp[l][r][0]，而在普通的拆区间时用的是dp[l][r][1]。另外，我们只需要在每次拆区间时加上中间的那个M即可，因为最初的M省略了，M只可能在区间中出现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;

const int maxn=54;

char s[maxn];

int dp[maxn][maxn][2];

inline bool check(int l,int len){
    for(int i=0;i<len/2;i++){
        if(s[l+i]!=s[l+len/2+i]){
            return 0;
        }
    }
    return 1;

}

int main(){
    cin>>(s+1);
    int n=strlen(s+1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            dp[i][j][0]=dp[i][j][1]=j-i+1;
    }
    for(int len=1;len<=n;len++){
        for(int i=1,r;i+len-1<=n;i++){
            r=i+len-1;
            if(len%2==0&&check(i,len)){
                dp[i][r][0]=min(dp[i][r][0],dp[i][(i+r)/2][0]+1);
            }
            for(int j=i;j<r;j++){
                dp[i][r][0]=min(dp[i][r][0],dp[i][j][0]+r-j);
            }
            for(int j=i;j<r;j++){
                dp[i][r][1]=min(dp[i][r][1],dp[i][j][1]+1+dp[j+1][r][1]);
            }
            dp[i][r][1]=min(dp[i][r][0], dp[i][r][1]);
        }
    }
    cout<<dp[1][n][1]<<endl;
}