题解

76 条题解

  • 4
    @ 2017-07-20 08:29:25

    #include<bits/stdc++.h>
    using namespace std;
    string s1,s2; int f[201][201];
    int main(){
    while (cin>>s1>>s2)
    {
    memset(f,0,sizeof(f));
    for (int i=1; i<=s1.length(); i++)
    for (int j=1; j<=s2.length(); j++)
    if (s1[i-1]==s2[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<<s1.length()+s2.length()-f[s1.length()][s2.length()]<<endl;
    }
    return 0;
    }

  • 3
    @ 2017-10-21 10:45:15
    //Simple LCS
    #include <bits/stdc++.h>
     using namespace std;
    int dp[200][200];
    int main()
    {
        char str1[200],str2[200];
        while(~scanf("%s%s",str1+1,str2+1))
        {
            int len1 = strlen(str1+1);
            int len2 = strlen(str2+1);
            memset(dp, 0, sizeof(dp));
            for(int i = 1; str1[i]; i++)
                for(int j = 1; str2[j]; j++)
                    if(str1[i] == str2[j])
                        dp[i][j] = dp[i-1][j-1]+1;
                    else
                        dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                
            //printf("%d\n", dp[len1][len2]);
            int ans = dp[len1][len2];
            ans = len1 + len2 - ans;
            printf("%d\n", ans);
        }
        return 0;
    }
    
  • 3
    @ 2017-06-03 16:30:43
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    
    int f[114][114];
    string a,b;
    
    int main()
    {
       while(cin>>a)
       {
           cin>>b;
           int alen=int(a.length());
           int blen=int(b.length());
           int flg=0;
           for(int i=0;i<blen;i++)
           {
               if(flg==0)
               {
                   if(a[0]==b[i])
                   {
                       flg=1;
                       f[0][i]=1;
                   }
                   else f[0][i]=0;
               }
               else f[0][i]=1;
           }
           flg=0;
           for(int i=0;i<alen;i++)
           {
               if(flg==0)
               {
                   if(b[0]==a[i])
                   {
                       flg=1;
                       f[i][0]=1;
                   }
                   else f[i][0]=0;
               }
               else f[i][0]=1;
           }
           for(int i=1;i<alen;i++)
           {
               for(int j=1;j<blen;j++)
               {
                   int tt=f[i-1][j]>f[i][j-1]?f[i-1][j]:f[i][j-1];
                   if(a[i]==b[j])
                   {
                       tt=f[i-1][j-1]+1;
                   }
                   f[i][j]=tt;
               }
           }
           cout<<alen+blen-f[alen-1][blen-1]<<endl;
       }
    }
    
    
  • 3
    @ 2017-05-08 07:59:28

    答案就是字符串的长度减去两者的LCS的长度即可
    所以直接写一个LCS的DP模板就好啦
    然后答案就出来咯

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <iomanip>
    #include <cstdlib>
    using namespace std;
    
    int f[101][101];
    char a[102],b[102];
    
    int main()
    {
        while(scanf("%s %s",a,b)==2)
        {
            int c1=strlen(a);
            int c2=strlen(b);
            for(int i=0;i<=c1;i++)
                f[i][0]=0;
            for(int i=0;i<=c2;i++)
                f[0][i]=0;
            for(int i=1;i<=c1;i++)
                for(int j=1;j<=c2;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]);
            int k=f[c1][c2];
            cout<<c1+c2-k<<endl;}
        return 0;
    }
         
    
  • 1
    @ 2019-03-10 10:27:26

    两串的长度和减去LCS的长度即可

    #include<cstdio>
    #include<algorithm>
    #include<string>
    #include<iostream>
    #include<cstring>
    using namespace std;
    int d[101][101];
    string a,b;
    int main(){
        ios::sync_with_stdio(false);
        while(cin>>a>>b){
            memset(d,0,sizeof(d));
            for(int i=0;i<a.size();i++){
                for(int j=0;j<b.size();j++){
                    if(a[i]==b[j]) d[i+1][j+1]=d[i][j]+1;
                    else d[i+1][j+1] = max(d[i+1][j],d[i][j+1]);
                }
            }
            cout<<a.size()+b.size()-d[a.size()][b.size()]<<endl;
        }
        return 0;
    }
    
    
    
  • 1
    @ 2018-04-18 13:02:10

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    #define q 250
    typedef long long ll;

    string a,b;
    int main()
    {

    while(cin>>a>>b)
    {
    ll f[q][q]={0},a1,b1;
    a1=a.size() ;
    b1=b.size() ;
    for(int i=1;i<=a1;i++)
    for(int j=1;j<=b1;j++)
    {
    if(a[i-1]==b[j-1])
    f[i][j]=f[i-1][j-1]+1;
    else
    f[i][j]=max(f[i][j-1],f[i-1][j]);

    }
    cout<<a1+b1-f[a1][b1]<<endl;

    }
    return 0;

    }

    模板题啊

  • 1
    @ 2016-03-16 20:06:20

    var
    s1,s:string;
    k,l1,l2,i,j:longint;
    a:array [0..105,0..105] of longint;
    begin
    while not(eof) do
    begin
    readln(s);
    k:=pos(' ',s);
    s1:=copy(s,1,k-1);
    delete(s,1,k);
    l1:=length(s1);
    l2:=length(s);
    fillchar(a,sizeof(a),0);
    for i:=1 to l1 do
    for j:=1 to l2 do
    if (s1[i]=s[j]) then a[i,j]:=a[i-1,j-1]+1
    else if (a[i,j-1]>a[i-1,j]) then a[i,j]:=a[i,j-1]
    else a[i,j]:=a[i-1,j];
    writeln(l1+l2-a[l1,l2]);
    end;
    end.

  • 0
    @ 2019-03-26 20:04:50

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

    int f[114][114];
    string a,b;

    int main()
    {
    while(cin>>a)
    {
    cin>>b;
    int alen=int(a.length());
    int blen=int(b.length());
    int flg=0;
    for(int i=0;i<blen;i++)
    {
    if(flg==0)
    {
    if(a[0]==b[i])
    {
    flg=1;
    f[0][i]=1;
    }
    else f[0][i]=0;
    }
    else f[0][i]=1;
    }
    flg=0;
    for(int i=0;i<alen;i++)
    {
    if(flg==0)
    {
    if(b[0]==a[i])
    {
    flg=1;
    f[i][0]=1;
    }
    else f[i][0]=0;
    }
    else f[i][0]=1;
    }
    for(int i=1;i<alen;i++)
    {
    for(int j=1;j<blen;j++)
    {
    int tt=f[i-1][j]>f[i][j-1]?f[i-1][j]:f[i][j-1];
    if(a[i]==b[j])
    {
    tt=f[i-1][j-1]+1;
    }
    f[i][j]=tt;
    }
    }
    cout<<alen+blen-f[alen-1][blen-1]<<endl;
    }
    }

  • 0
    @ 2018-08-06 16:19:31
    #include <bits/stdc++.h>
    using namespace std;
    #define FOR(i,n) for (int i=1;i<=n;i++)
    #define REP(i,a,b) for (int i=a;i<=b;i++)
    #define pb push_back
    #define mp make_pair
    #define ll long long
    const int N=100000+10;
    const int inf=0x3f3f3f3f;
    const ll mod=7654321;
    const double PI=3.1415926;
    const double eps=1e-8;
    
    string s,s2;
    int f[101][101];
    int main() {
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
        while (cin>>s>>s2) {
            memset(f,0,sizeof f);
            int n=s.size(),m=s2.size();
            FOR(i,n) FOR(j,m) {
                f[i][j]=max(f[i][j],f[i][j-1]);
                f[i][j]=max(f[i][j],f[i-1][j]);
                if (s[i-1]==s2[j-1]) f[i][j]=max(f[i][j],1+f[i-1][j-1]);
            }
            cout<<n+m-f[n][m]<<endl;
        }
        return 0;
    }
    
  • 0
    @ 2017-09-23 11:31:40
    while True:
        try:
            a, b = input().split()
            dp =  [[0 for i in range(101)] for i in range(101)]
            for i in range(len(a)+1):
                for j in range(len(b)+1):
                    dp[i][j] = 0
            for i in range(1, len(a)+1):
                for j in range(1, len(b)+1):
                    if a[i-1] == b[j-1]:
                        dp[i][j] = dp[i-1][j-1] + 1
                    else:
                        dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            print(len(a) + len(b) - dp[len(a)][len(b)])
        except EOFError:
            break
    
    
  • 0
    @ 2017-05-03 17:34:39

    逗我就一个数据点???
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    using namespace std;
    int max(int x,int y)
    {
    return x>y?x:y;
    }
    int main()
    {
    char s[101],t[101];
    int f[101][101];
    while(cin>>s>>t)
    {
    memset(f,0,sizeof(f));
    for(int i=0;i<strlen(s);i++){
    for(int j=0;j<strlen(t);j++){
    if(s[i]==t[j]) f[i+1][j+1]=f[i][j]+1;
    else f[i+1][j+1]=max(f[i][j+1],f[i+1][j]);
    }
    }
    cout<<strlen(s)+strlen(t)-f[strlen(s)][strlen(t)]<<endl;
    }
    return 0;
    }

  • 0
    @ 2016-09-23 15:08:40

    ans=字符串长度和-LCS(相同字符个数)

  • 0
    @ 2016-08-16 00:12:52
  • 0
    @ 2016-05-11 12:29:04

    SCS=长度和-LCS
    ```pascal
    uses math;
    function lcs(a,b:string):integer;
    var dp:array[0..101,0..101] of integer;
    i,j:integer;
    begin
    for i:=0 to length(a) do dp[i,0]:=0;
    for j:=0 to length(b) do dp[0,j]:=0;
    for i:=1 to length(a) do
    for j:=1 to length(b) do
    if a[i]=b[j] then dp[i,j]:=dp[i-1,j-1]+1
    else dp[i,j]:=max(dp[i-1,j],dp[i,j-1]);
    lcs:=dp[length(a),length(b)];
    end;

    var i,z:integer;t:string;
    begin
    while not eof do begin
    readln(t);
    for i:=1 to length(t) do
    if t[i]=' ' then begin z:=i;break end;
    writeln(length(t)-1-lcs(copy(t,1,z-1),copy(t,z+1,length(t)-z)));
    end;
    end.

    ```

  • 0
    @ 2016-05-09 18:11:49

    一开始被坑得好惨
    ```c++
    #include<iostream>
    #include<cstdio>
    #include<string>
    #include<algorithm>
    using namespace std;

    string ss1, ss2;
    int ans;
    int f[110][110];

    void lcs () {
    int l1 = ss1.size();
    int l2 = ss2.size();
    for (int i = 0; i < l1; i++) {
    for (int j = 0; j < l2; j++) {
    if (ss1[i] == ss2[j]) f[i + 1][j + 1] = f[i][j] + 1;
    else {
    f[i + 1][j + 1] = max (f[i + 1][j], f[i][j + 1]);
    }
    }
    }
    ans = l1 + l2 - f[l1][l2];
    }

    int main ()
    {
    //freopen ("in.txt", "r", stdin);
    while (cin >> ss1 >> ss2) {
    lcs();
    cout << ans << endl;
    }
    return 0;
    }
    ```

  • 0
    @ 2016-03-21 17:08:40

    一个点?
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 544 KiB, score = 100

    Accepted, time = 0 ms, mem = 544 KiB, score = 100

  • 0
    @ 2016-02-17 15:55:49
    #include<stdio.h>
    #include<string.h>
    char a[105],b[105];
    int lcs[105][105]={0};
    inline int max(int a,int b){ return a>b?a:b; }
    int main(){
        while(~scanf("%s %s",a,b)){
            int n=strlen(a);
            int m=strlen(b);
            memset(lcs,0,sizeof lcs);
            for(int i=0;i<n;++i)
                for(int j=0;j<m;++j)
                    if(a[i]==b[j]) lcs[i+1][j+1]=lcs[i][j]+1;
                    else lcs[i+1][j+1]=max(lcs[i][j+1],lcs[i+1][j]);
            printf("%d\n",n+m-lcs[n][m]);
        }
    }
    
  • 0
    @ 2016-02-17 15:55:19

    **
    #include<stdio.h>
    #include<string.h>
    char a[105],b[105];
    int lcs[105][105]={0};
    inline int max(int a,int b){ return a>b?a:b; }
    int main(){
    while(~scanf("%s %s",a,b)){
    int n=strlen(a);
    int m=strlen(b);
    memset(lcs,0,sizeof lcs);
    for(int i=0;i<n;++i)
    for(int j=0;j<m;++j)
    if(a[i]==b[j]) lcs[i+1][j+1]=lcs[i][j]+1;
    else lcs[i+1][j+1]=max(lcs[i][j+1],lcs[i+1][j]);
    printf("%d\n",n+m-lcs[n][m]);
    }
    }
    **

  • 0
    @ 2015-12-13 11:33:18

    program p1111;
    var a:array[0..1001,0..1001] of integer;
    c:char;
    s,ss:string;
    i,j,k,m,n,js:longint;
    begin
    assign(input,'p1111.in');
    assign(output,'p1111.out');
    reset(input);
    rewrite(output);
    while not eof do
    begin
    fillchar(a,sizeof(a),0);
    i:=1;
    read(c);s:='';
    while c<>' ' do
    begin
    s:=s+c;
    i:=i+1;
    read(c);
    end;
    readln(ss);
    m:=i-1;
    n:=length(ss);
    for i:=1 to m do
    begin
    for j:=1 to n do
    begin
    if s[i]=ss[j] then a[i,j]:=a[i-1,j-1]+1
    else
    begin
    if a[i-1,j]>a[i,j-1] then a[i,j]:=a[i-1,j]
    else a[i,j]:=a[i,j-1];
    end;
    end;
    end;
    writeln(m+n-a[m,n]);
    end;
    close(input);
    close(output);
    end.
    瞬间爆炸,完成AC!

  • 0
    @ 2015-08-24 14:19:26

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <vector>
    using namespace std;
    typedef long long LL;
    const int N = 110;
    const int M = 150;
    int dp[N][N];
    int main()
    {
    char a[110],b[110];
    while(~scanf("%s%s",&a,&b))
    {
    memset(dp,0,sizeof(dp));
    int len1 = strlen(a);
    int len2 = strlen(b);
    for(int i = 0; i < len1; i++)
    {
    for(int j = 0; j < len2; j++)
    {
    if(a[i] == b[j])
    dp[i+1][j+1] = dp[i][j] + 1;
    else
    dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]);
    }
    }
    printf("%d\n",len1+len2-dp[len1][len2]);
    }
    }

信息

ID
1111
难度
4
分类
动态规划 | LCS 点击显示
标签
递交数
2781
已通过
1249
通过率
45%
被复制
4
上传者