2 条题解

  • 0
    @ 2025-10-8 16:48:59

    第一个题解：

    #include<bits/stdc++.h>
using namespace std;
char s1[110],s2[110],s3[110],b[110];
int f[110][110][110];
struct node
{
    int x,y,z;
}root[110][110][110];
 
int main()
{
    int n1,n2,n3,K;
    scanf("%s",s1+1);n1=strlen(s1+1);
    scanf("%s",s2+1);n2=strlen(s2+1);
    scanf("%s",s3+!);n!3=strlen(s3+1);
    f[0][0][0]=0;
     
    for(int i=1; i<=n1;i++)
      for(int j=1;j<=n2;j++)
          for(int k=1;k<=n3;k++)
            if(s1[i]==s2[j]&& s2[j]==s3[k])
            {
                f[i][j][k]=f[i-1][j-1][k-1]+1;
                root[i][j][k].x=i;
                root[i][j][k].y=j;
                root[i][j][k].z=k; 
            }
            else
            {
                if(f[i-1][j][k]>f[i][j][k])
                {
                    f[i][j][k]=f[i-1][j][k];
                    root[i][j][k]=root[i-1][j][k];
                }
                if(f[i][j-1][k]>f[i][j][k])
                {
                    f[i][j][k]=f[i][j-1][k];
                    root[i][j][k]=root[i][j-1][k];
                }
                if(f[i][j][k-1]>f[i][j][k])
                {
                    f[i][j][k]=f[i][j][k-1];
                    root[i][j][k]=root[i][j][k-1];
                }
            }
     
    printf("%d\n",f[n1][n2][n3]); 
    int x=root[n1][n2][n3].x;
    int y=root[n1][n2][n3].y;
    int z=root[n1][n2][n3].z;
    int len=0;
    while(f[x][y][z]>0)
    {
        b[++len]=s1[x];
        x--;y--;z--;
        int tx=root[x][y][z].x;
        int ty=root[x][y][z].y;
        int tz=root[x][y][z].z;
        x=tx;y=ty;z=tz;
    }
    for(int i=len;i>=1;i--) printf("%c",b[i]);
    printf("\n");
    return 0;
}

    yzc代码：

    #include<bits/stdc++.h>
using namespace std;
const int N=110;
char a[N],b[N],c[N];
int f[N][N][N];
struct f
{
    int x,y,z;
}root[N][N][N];
int main()
{
    cin>>a+1>>b+1>>c+1;
    int n1=strlen(a+1);int n2=strlen(b+1);int n3=strlen(c+1);
     
    memset(f,0,sizeof(f));
     
    for(int i=1;i<=n1;i++)
        for(int j=1;j<=n2;j++)
            for(int k=1;k<=n3;k++)
            {
                if(a[i]==b[j]&&b[j]==c[k])
                {
                    f[i][j][k]=f[i-1][j-1][k-1]+1;
                    root[i][j][k].x=i;
                    root[i][j][k].y=j;
                    root[i][j][k].z=k;
                }
                else
                {
                    int x=f[i-1][j][k],y=f[i][j-1][k],z=f[i][j][k-1];
                    if(x>=y&&x>=z)
                    {
                        f[i][j][k]=x;
                        root[i][j][k]=root[i-1][j][k];
                 
                    }
                    else if(y>=x&&y>=z)
                    {
                        f[i][j][k]=y;
                        root[i][j][k]=root[i][j-1][k];
                     
                    }
                    else
                    {
                        f[i][j][k]=z;
                        root[i][j][k]=root[i][j][k-1];
                         
                    }
                }
            }
             
    cout<<f[n1][n2][n3]<<endl;
    int len=0;char s[N];
    int x=root[n1][n2][n3].x;
    int y=root[n1][n2][n3].y;
    int z=root[n1][n2][n3].z;
    while(f[x][y][z]>0)
    {
        s[++len]=a[x];
        x--;y--;z--;
        int tx=root[x][y][z].x;
        int ty=root[x][y][z].y;
        int tz=root[x][y][z].z;
        x=tx;y=ty;z=tz;
    }
    for(int i=len;i>=1;i--)cout<<s[i];
    return 0;
}
    • 0
      @ 2025-10-8 16:48:35 
      #include<bits/stdc++.h>
using namespace std;
char s1[110],s2[110],s3[110],b[110];
int f[110][110][110];
struct node
{
    int x,y,z;
}root[110][110][110];
 
int main()
{
    int n1,n2,n3,K;
    scanf("%s",s1+1);n1=strlen(s1+1);
    scanf("%s",s2+1);n2=strlen(s2+1);
    scanf("%s",s3+1);n3=strlen(s3+1);
    f[0][0][0]=0;
     
    for(int i=1; i<=n1;i++)
      for(int j=1;j<=n2;j++)
          for(int k=1;k<=n3;k++)
            if(s1[i]==s2[j]&& s2[j]==s3[k])
            {
                f[i][j][k]=f[i-1][j-1][k-1]+1;
                root[i][j][k].x=i;
                root[i][j][k].y=j;
                root[i][j][k].z=k; 
            }
            else
            {
                if(f[i-1][j][k]>f[i][j][k])
                {
                    f[i][j][k]=f[i-1][j][k];
                    root[i][j][k]=root[i-1][j][k];
                }
                if(f[i][j-1][k]>f[i][j][k])
                {
                    f[i][j][k]=f[i][j-1][k];
                    root[i][j][k]=root[i][j-1][k];
                }
                if(f[i][j][k-1]>f[i][j][k])
                {
                    f[i][j][k]=f[i][j][k-1];
                    root[i][j][k]=root[i][j][k-1];
                }
            }
     
    printf("%d\n",f[n1][n2][n3]); 
    int x=root[n1][n2][n3].x;
    int y=root[n1][n2][n3].y;
    int z=root[n1][n2][n3].z;
    int len=0;
    while(f[x][y][z]>0)
    {
        b[++len]=s1[x];
        x--;y--;z--;
        int tx=root[x][y][z].x;
        int ty=root[x][y][z].y;
        int tz=root[x][y][z].z;
        x=tx;y=ty;z=tz;
    }
    for(int i=len;i>=1;i--) printf("%c",b[i]);
    printf("\n");
    return 0;
}

      yzc代码： 
      #include<bits/stdc++.h>
using namespace std;
const int N=110;
char a[N],b[N],c[N];
int f[N][N][N];
struct f
{
    int x,y,z;
}root[N][N][N];
int main()
{
    cin>>a+1>>b+1>>c+1;
    int n1=strlen(a+1);int n2=strlen(b+1);int n3=strlen(c+1);

      memset(f,0,sizeof(f));
 
for(int i=1;i&lt;=n1;i++)
    for(int j=1;j&lt;=n2;j++)
        for(int k=1;k&lt;=n3;k++)
        {
            if(a[i]==b[j]&amp;&amp;b[j]==c[k])
            {
                f[i][j][k]=f[i-1][j-1][k-1]+1;
                root[i][j][k].x=i;
                root[i][j][k].y=j;
                root[i][j][k].z=k;
            }
            else
            {
                int x=f[i-1][j][k],y=f[i][j-1][k],z=f[i][j][k-1];
                if(x&gt;=y&amp;&amp;x&gt;=z)
                {
                    f[i][j][k]=x;
                    root[i][j][k]=root[i-1][j][k];
             
                }
                else if(y&gt;=x&amp;&amp;y&gt;=z)
                {
                    f[i][j][k]=y;
                    root[i][j][k]=root[i][j-1][k];
                 
                }
                else
                {
                    f[i][j][k]=z;
                    root[i][j][k]=root[i][j][k-1];
                     
                }
            }
        }
         
cout&lt;&lt;f[n1][n2][n3]&lt;&lt;endl;
int len=0;char s[N];
int x=root[n1][n2][n3].x;
int y=root[n1][n2][n3].y;
int z=root[n1][n2][n3].z;
while(f[x][y][z]&gt;0)
{
    s[++len]=a[x];
    x--;y--;z--;
    int tx=root[x][y][z].x;
    int ty=root[x][y][z].y;
    int tz=root[x][y][z].z;
    x=tx;y=ty;z=tz;
}
for(int i=len;i&gt;=1;i--)cout&lt;&lt;s[i];
return 0;

      

      }
      </p>
      • 1

      *【动态规划：区间三维一边推】最长公共子序列3️⃣

      信息

      ID
      239
      时间
      1000ms
      内存
      128MiB
      难度
      5
      标签
      递交数
      135
      已通过
      50
      上传者
      1. Language
      2. 兼容模式
      3. 主题
      3. Worker 0, 5ms
      4. Powered by Hydro v5.0.1 Community