3 条题解

  • 1
    @ 2025-4-20 20:20:42
    #include<bits/stdc++.h>
    using namespace std;
    const int N = 200 + 10;
    string a,b,ans;
    struct node
    {
    	int num;
    	int i;
    	int j;
    }dp[N][N];
    int main(){
    	cin >> a>>b;
    	int lena = a.size();
    	int lenb = b.size();
    	for(int i = 1;i <= lena;i++)
    	{
    		for(int j = 1;j <= lenb;j++)
    		{
    	        if(a[i - 1] == b[j - 1])
    	        {
    	        	dp[i][j].num = dp[i - 1][j - 1].num + 1;
    	        	dp[i][j].i = i;
    	        	dp[i][j].j = j;
    			}
    			else if(dp[i - 1][j].num > dp[i][j - 1].num)
    			{
    	        	dp[i][j].num = dp[i - 1][j].num;
    	        	dp[i][j].i = dp[i - 1][j].i;
    	        	dp[i][j].j = dp[i - 1][j].j;
    			}
    			else 
    			{
    	        	dp[i][j].num = dp[i][j - 1].num;
    	        	dp[i][j].i = dp[i][j - 1].i;
    	        	dp[i][j].j = dp[i][j - 1].j;
    			}
    		}
    	} 
        cout << dp[lena][lenb].num << endl;
        for(int i = dp[lena][lenb].i,j = dp[lena][lenb].j,tmp;i | j;i = tmp)
        {
        	ans = a[i - 1] + ans;
        	tmp = dp[i - 1][j - 1].i;
        	j = dp[i - 1][j - 1].j;
    	}
    	cout << ans;
    	return 0;
    }
    
    • 0
      @ 2022-11-12 14:21:57
      #include <iostream>
      #include <algorithm>
      #include <cstdio>
      #include <cstring>
      #include <string>
      #include <iomanip>
      #include <cmath>
      #include <queue>
      #include <map>
      #include <stack>
      #include <vector>
      using namespace std;
      #define long long LL
      const int N = 1e3+5;
      char a[N],b[N];
      int lena,lenb,dp[N][N];
      int main(){
      	scanf("%s%s" , a + 1, b + 1);
      	lena = strlen(a + 1);
      	lenb = strlen(b + 1);
      	for (int i = 1;i<=lena;i++)
      	{
      		for (int j = 1;j<=lenb;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[lena][lenb];
      	return 0;
      }
      
      • -4
        @ 2023-4-9 14:56:11

        #include <bits/stdc++.h> using namespace std; int f[10001][10001]; void lcs(string c,string d,int o,int k){ if(o0||k0) return; if(c[o-1]==d[k-1]){ lcs(c,d,o-1,k-1); cout<<c[o-1]; } else if(f[o-1][k]>f[o][k-1])lcs(c,d,o-1,k); else lcs(c,d,o,k-1); } int main(){ string a,b; cin>>a>>b; int n=a.size(); int m=b.size(); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i-1]==b[j-1])f[i][j]=f[i-1][j-1]+1; else f[i][j]=max(f[i-1][j],f[i][j-1]); } } cout<<f[n][m]; cout<<endl; lcs(a,b,n,m); return 0; }

        • 1

        信息

        ID
        1508
        时间
        1000ms
        内存
        256MiB
        难度
        8
        标签
        递交数
        226
        已通过
        36
        上传者