2020北京ICPC网络选拔赛Round1-J

2020北京ICPC网络选拔赛Round1-J

十一月 03, 2020

Matrix Subtraction

  • 题意

给出一个字符串s和字符串t (长度均小于2000)

从他们中分别选出两个子序列x y

要求符合：

  • x的字典序小于y
  • 要求|x|+|y|最大

求|x|+|y|的最大值

  • 题解

x的字典序小于y当且仅当：

  • x是y的前缀且|x|<|y|
  • x不是y的前缀 且存在某个位置i 使得x和y的前i-1个字符相同 $x_i$<$y_i$

从s和t串中得到的x和y必须符合上述条件

发现无论哪种情况 都需要求出LongestCommonSequence($s_1$~$s_i$, $t_1$~ $t_j$)

对于第一种情况|x|+|y|的最大值=max{LCS($s_1$~$s_i$, $t_1$~ $t_j$)+$len_t-j$}

即x是y的前缀同时将$t_{j+1}$之后的字符全给归s

对于第二种情况当$s_i<t_j$时以这一位字符作为 x和y的位置 i (上文提到的位置 i )

|x|+|y|的最大值=max{LCS($s_1​$~ $s_{i-1}​$,$t_1​$~$t_{j-1}​$)+$len_t-j+1​$+$len_s-i+1​$}

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
//#define P pair<ll,ll>
const int Max=2000+5;
const int Mod=1e9+7;
const int inf=0x3f3f3f3f;

int dp[Max][Max];
int main(){
    Turnoff;
    string s,t;
    while(cin>>s>>t){
        int lens=s.size(),lent=t.size();
        int ans=lent;
        for(int i=0;i<lens;i++){
            for(int j=0;j<lent;j++){
                if(s[i]==t[j])dp[i+1][j+1]=dp[i][j]+1;
                else dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
                ans=max(ans,dp[i+1][j+1]*2+lent-j-1);
                if(s[i]<t[j])ans=max(ans,dp[i][j]*2+lens-i+lent-j);
            }
        }
        cout<<ans<<endl;
    } 
}