1363F字符串dp

Posted on | In

这题真的长见识了哈哈

https://codeforces.com/contest/1363/problem/F

给字符串s、t，可对s进行局部右旋操作，求将s转变成t的最小操作数。

经过分析我们发现，右旋的本质是将右边的某个字符挪到左边。我们从后往前尝试满足t字符串的匹配。例如首先看s[n]是否等于t[n]，如果不相等，将s[n]拿起来准备插入前面的某个位置，注意这时它处于“悬而未决”状态，接下来我们不断前移s的指针i去匹配t的后缀直至全部匹配，每次都尝试三种情况：

直接把s[i]拿起、i–，花费++

如果s[i]=t[j]则直接匹配，双方指针都向前挪动、

如果悬而未决的元素中有能匹配t[j]的，则用它去匹配，然后j–，这个判断需要记录字符的后缀和。

然后我们令dp[i][j]表示从两个指针分别等于i和j时开始到整个匹配过程结束所需的花费，根据前述三种情况，这个dp最适合用递归实现。

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;

const int maxn=2002;

int T,n;
char s[maxn],t[maxn];
int cache[maxn][maxn];
int sufs[maxn][26],suft[maxn][26];

int dp(int i,int j){
    //dp(i,j)的含义是：t[j+1..n]后缀已经得到匹配的情形下，用s[1..i]以及悬而未决的j-i个元素依次匹配t[j]..t[1]的最小花费
    //悬而未决的元素可以放在任何位置，所以dp[0][j]=0，这时s已经没有可拿起的元素，直接把悬而未决的元素按照t[1..j]排列即可
    if(~cache[i][j])
        return cache[i][j];
    int res=2e9;
    if(i){
        res=1+dp(i-1,j);
        if(s[i]==t[j]){
            res=min(res,dp(i-1,j-1));
        }
        int ch=t[j]-'a';
        if(sufs[i+1][ch]>suft[j+1][ch]){
            res=min(res,dp(i,j-1));
        }
    }
    return cache[i][j]=res;
}

int main(){
    cin>>T;
    while(T--){
        cin>>n>>(s+1)>>(t+1);
        for(int j=0;j<=n;j++)
            cache[0][j]=0;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=n;j++){
                cache[i][j]=-1;
            }
        }
        for(int i=0;i<26;i++){
            sufs[n+1][i]=0;
            suft[n+1][i]=0;
        }
        for(int i=n;i;i--){
            for(int j=0;j<26;j++){
                sufs[i][j]=sufs[i+1][j];
                suft[i][j]=suft[i+1][j];
            }
            sufs[i][(int)(s[i]-'a')]++;
            suft[i][(int)(t[i]-'a')]++;
        }
        bool f=true;
        for(int i=0;i<26;i++){
            if(sufs[1][i]!=suft[1][i]){
                f=false;
                break;
            }
        }
        int ans=(f?dp(n,n):-1);
        cout<<ans<<endl;
    }
}

还有一种做法好理解，我们设想，如果允许左旋和右旋，那么直接找到两者最长公共子序列长度len，然后n-len就是答案，因为剩余相对关系混乱的元素只需要移动一次就能排好。然鹅现在只支持右旋，所以我们在求最长公共子序列时受到限制，在+1时需要保证s右边字符都大于等于t的右边字符数，因为混乱元素只能向左移不能向右。