docker installation and fast entry (Mac) BUPT

2023-01-06   ES  

1110 – An Easy LCS
PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 32 MB
LCS means ‘Longest Common Subsequence’ that means two non-empty strings are given; you have to find the Longest Common Subsequence between them. Since there can be many solutions, you have to print the one which is the lexicographically smallest. Lexicographical order means dictionary order. For example, ‘abc’ comes before ‘abd’ but ‘aaz’ comes before ‘abc’.

Input
Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a blank line. The next two lines will contain two strings of length 1 to 100. The strings contain lowercase English characters only.

Output
For each case, print the case number and the lexicographically smallest LCS. If the LCS length is 0 then just print ‘:(‘.

Sample Input
Output for Sample Input
3

ab
ba

zxcvbn
hjgasbznxbzmx

you
kjhs
Case 1: a
Case 2: zxb
Case 3: 🙁

Question ideas: Just use LCS templates plus the record path.

But in the process of doing this question, it has been relying, and it is okay to run locally. After finding it carefully, I found that I traveled from I = 0 and J = 0, and the situation of DP [i-1] [J-1] was re, but DEV is not explosive: (

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 110;
int dp[N][N];
char str1[N],str2[N],ans[N][N][N];

int main(){
    
    int T;
    scanf("%d",&T);
    for(int t=1;t<=T;t++){
        
        memset(dp,0,sizeof(dp));
        memset(ans,0,sizeof(ans));
        
        scanf("%s %s",str1+1,str2+1);
        
        int len1 = strlen(str1+1),len2 = strlen(str2+1);
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(str1[i]==str2[j]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    strcpy(ans[i][j],ans[i-1][j-1]);
                    ans[i][j][dp[i-1][j-1]] = str1[i];
                    ans[i][j][dp[i][j]] = '\0';                    
                }else{
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                    if(dp[i-1][j]<dp[i][j-1]){
                        strcpy(ans[i][j],ans[i][j-1]);
                    }else if(dp[i-1][j]>dp[i][j-1]){
                        strcpy(ans[i][j],ans[i-1][j]);
                    }else{
                        if(strcmp(ans[i][j-1],ans[i-1][j])>0){
                            strcpy(ans[i][j],ans[i-1][j]);
                        }else{
                            strcpy(ans[i][j],ans[i][j-1]);
                        }
                    }
                }
            }
        }
        if(strlen(ans[len1][len2])==0)printf("Case %d: :(\n",t);// strcpy(ans[len1-1][len2-1],":(\0");
        else printf("Case %d: %s\n",t,ans[len1][len2]);
        
    }
    
    
} 

Reprinted: https://www.cnblogs.com/yuanshixingdan/p/5568826.html

source

Related Posts

Android compilation system analysis, detailed explanation of the call order of the MK file after executing Make Bootimage

Read the local JSON file through AJAX to indicate the cause and solution of the cross -domain

[Optimization] XXXX Management System ORA-04031 Question Diagnosis Optimization

Solr4.10.3 Installation configuration

docker installation and fast entry (Mac) BUPT

Random Posts

Configure the OpenCV development environment under QT 5.7

python3 network crawler (1) -The novel crawling (take the website novel as an example) isana) Isana

Front -end H5 Enterprise WeChat third -party application development shallow talk (1) Enterprise WeChat front -end development MR

avro technology application 3. Use Hive table to process AVRO data Mike

2021-10-13 Daily Question: Leetcode 412. FIZZ Buzz