<span>Atcoder F - LCS (DP-最长公共子序列，输出字符串)</span>
F - LCS
Time Limit: 2 sec / Memory Limit: 1024 MB
Score : <var>100100</var> points
Problem Statement
You are given strings <var>ss</var> and <var>tt</var>. Find one longest string that is a subsequence of both <var>ss</var> and <var>tt</var>.
Notes
A subsequence of a string <var>xx</var> is the string obtained by removing zero or more characters from <var>xx</var> and concatenating the remaining characters without changing the order.
Constraints
- <var>ss</var> and <var>tt</var> are strings consisting of lowercase English letters.
- <var>1≤|s|,|t|≤30001≤|s|,|t|≤3000</var>
Input
Input is given from Standard Input in the following format:
<var>ss</var> <var>tt</var>
Output
Print one longest string that is a subsequence of both <var>ss</var> and <var>tt</var>. If there are multiple such strings, any of them will be accepted.
Sample Input 1 Copy
Copy
axyb abyxb
Sample Output 1 Copy
Copy
axb
The answer is axb&nbs***bsp;ayb; either will be accepted.
Sample Input 2 Copy
Copy
aa xayaz
Sample Output 2 Copy
Copy
aa
Sample Input 3 Copy
Copy
a z
Sample Output 3 Copy
Copy
The answer is (an empty string).
Sample Input 4 Copy
Copy
abracadabra avadakedavra
Sample Output 4 Copy
Copy
aaadara
题意：给定两个字符串s和t，让你求出这两个字符串的最长公共子序列，并输出最长公共子序列。
思路：先通过DP求出LCS的DP信息，然后再根据DP信息输出对应的字符。
裸题主要看思路。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) using namespace std; typedef long long ll; inline void getInt(int* p); const int maxn=1000010; const int inf=0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ int dp[3050][3050]; char a[maxn]; char b[maxn]; int n,m; int c[maxn]; int pre[maxn]; int lis[maxn]; int main() { scanf("%s",a); scanf("%s",b); n=strlen(a); m=strlen(b); for(int i=n-1;i>=0;i--) { for(int j=m-1;j>=0;j--) { if(a[i]==b[j]) { dp[i][j]=dp[i+1][j+1]+1; }else { dp[i][j]=max(dp[i+1][j],dp[i][j+1]); } } } // cout<<dp[n-1][m-1]<<endl; int i=0; int j=0; while(i<n&&j<m) { if(a[i]==b[j]) { putchar(a[i]); i++; j++; }else if(dp[i][j]==dp[i+1][j]) { i++; }else { j++; } } return 0; } inline void getInt(int* p) { char ch; do { ch = getchar(); } while (ch == ' ' || ch == '\n'); if (ch == '-') { *p = -(getchar() - '0'); while ((ch = getchar()) >= '0' && ch <= '9') { *p = *p * 10 - ch + '0'; } } else { *p = ch - '0'; while ((ch = getchar()) >= '0' && ch <= '9') { *p = *p * 10 + ch - '0'; } } }
58集团稳定性 2人发布
投递58集团等公司10个岗位 >
深信服三面2人在聊
查看2道真题和解析