题解

1 条题解

  • 0
    @ 2017-03-09 21:39:12
    #include<cstdio>
    #include<algorithm> 
    using namespace std;
    int up[203],down[203],f[203][203],ip[203][203],jp[203][203];
    int n,m;
    
    int main()
    { 
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        scanf("%d",&up[i]);
        for(int i=1;i<=m;i++)
        scanf("%d",&down[i]);
        
        for(int i=1;i<=n;i++){
            for(int j=2;j<=m;j++){
                if(down[j-1]==up[i]) jp[i][j]=j-1; 
                else jp[i][j]=jp[i][j-1];
            }
        }
        for(int i=2;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(up[i-1]==down[j]) ip[i][j]=i-1; 
                else ip[i][j]=ip[i-1][j];
            }
        }
        
        for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            f[i][j]=max(f[i-1][j-1],f[i][j]);
            
            if(up[i]!=down[j])
            {   int x=ip[i][j],y=jp[i][j];
                if(x!=0&&y!=0)
                f[i][j]=max(f[i][j],f[x-1][y-1]+2);
            }
            
            
        }
        printf("%d",f[n][m]);
        
        return 0;
    }
    
  • 1

信息

难度
10
分类
(无)
标签
(无)
递交数
2
已通过
0
通过率
0%
上传者