SubsequencePair

NC213136. SubsequencePair

描述

Bobo has two strings s and t. He would like to choose two subsequences x from s and y from t such that:

+ x is lexicographically smaller than or equal to y.
+ The sum of |x| and |y| is maximal, where |s| denotes the length of the string s.

Note that:

+ Both x and y could be empty string.
+ A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.
+ String x is lexicographically less than string y, if either x is a prefix of y (and $x \ne y$ ), or there exists such i ( $1 \le i \le \min(|x|, |y|)$ ), that $x_i < y_i$ , and for any j ( $1 \le j < i$ ) $x_j = y_j$ .

输入描述

The input consists of several test cases terminated by end-of-file. For each test case:

The first line contains a string s. The second line contains a string t.

* 
* 
* The sum of |s| does not exceed 20000.
* The sum of |t| does not exceed 20000.
* Both the strings consist only of English lowercase letters.

输出描述

For each test case, output the sum of |x| and |y|.

示例1

输入:

aaaa
bbbb
abcd
abca
abcd
abcd

输出:

8
7
8

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 55ms, 内存消耗: 15992K, 提交时间: 2020-11-02 14:31:54

#include<bits/stdc++.h>
using namespace std;
int dp[2005][2005];
char s[2005],t[2005];
int main(){
	while(~scanf("%s%s",s+1,t+1)){
		int ns=strlen(s+1),nt=strlen(t+1),ans=0;
		for(int i=1;i<=ns;++i)
			for(int j=1;j<=nt;++j){
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
				if(s[i]==t[j])
					dp[i][j]=dp[i-1][j-1]+2,ans=max(ans,dp[i][j]+nt-j);
				else if(s[i]<t[j])ans=max(ans,dp[i-1][j-1]+2+ns+nt-i-j);
			}
		ans=max(ans,dp[ns][nt]);
		printf("%d\n",max(ans,nt));
	}
}

上一题

下一题

详情