Koios1143的筆記

Atcoder DP Contest pF

發表於 更新於 分類於

Atcoder DP Contest pF

題敘

https://atcoder.jp/contests/dp/tasks/dp_f
給兩個字串，問兩字串的LCS，並輸出最大的LCS

想法

把兩個字串拆成:

s = sub1 + e1
t = sub2 + e2

另$LCS(i,j)$ 表示 $s[0i]$ 和 $t[0j]$ 的LCS長度
分成四種情況討論

  1. LCS包含 $e1$ ，不含 $e2$
    $LCS(s,t) = LCS(s,sub2)$
  2. LCS包含 $e1$ ，包含 $e2$
    $LCS(s,t) = LCS(sub1,sub2)+1$
  3. LCS不含 $e1$ ，不含 $e2$
    $LCS(s,t) = LCS(sub1,sub2)$
  4. LCS不含 $e1$ ，包含 $e2$
    $LCS(s,t) = LCS(sub1,t)$

總的來說，定義 $DP[i][j]$ 表示$LCS(i,j)$的長度
則有轉移式
$DP[i][j] = DP[i-1][j-1]+1\ ,s[i]=t[j]$
$DP[i][j] = max(DP[i-1][j], DP[i],[j-1])\ ,s[i] \neq t[j]$
且已知
$DP[i][0] = 0, DP[0][j] = 0$

這邊能獲得的僅僅是LCS長度，但題目所求的是字串
可以另外開一個陣列紀錄他是從哪裡轉移過來，最後遞迴輸出結果即可

Code

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
//By Koios1143
#include<bits/stdc++.h>
#define LL long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;
string s,t;
int dp[3005][3005],from[3005][3005];

void print_LCS(int i,int j){
	if(i==0 || j==0)
		return;
	if(from[i][j] == 0){
		print_LCS(i-1,j-1);
		cout<<s[i-1];
	}
	else if(from[i][j] == 1)
		print_LCS(i-1,j);
	else
		print_LCS(i,j-1);
}

int main(){
	IOS
	while(cin>>s>>t){
		for(int i=0 ; i<3005 ; i++){
			dp[i][0] = dp[0][i] = 0;
		}
		for(int i=1 ; i<=s.size() ; i++){
			for(int j=1 ; j<=t.size() ; j++){
				if(s[i-1] == t[j-1]){
					dp[i][j] = dp[i-1][j-1]+1;
					from[i][j]=0;
				}
				else{
					if(dp[i-1][j] > dp[i][j-1])
						from[i][j]=1;
					else
						from[i][j]=2;
					dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
				}
			}
		}
		print_LCS(s.size(),t.size());
	}
	return 0;
}

複雜度

有 $len(s)*len(t)$ 種狀態，每種狀態轉移時間複雜度為 $O(1)$
DP複雜度為 $O(len(s)*len(t))$
輸出複雜度大約為 $O(len(s)+len(t))$
總複雜度 $O(len(s)*len(t))$