文章

39

粉丝

74

获赞

1

访问

20.4k

头像
最长连续公共子序列 题解:Output Limit Exceeded
P1730 西安电子科技大学2018年机试题
发布于2024年3月23日 14:10
阅读数 732

#include <stdio.h>
#include <stdlib.h>
int m,n;
char s1[105],s2[105];
int dp[105][105];

int max1(int a,int b)
{
    if(a>=b)return a;
    else return b;
}

int main()
{
    while(scanf("%s%s",s1,s2)!=EOF){
        int len1=strlen(s1);
        int len2=strlen(s2);
        int max=0;
        int start=0;
        dp[0][0]=0;
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(s1[i-1]==s2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=max1 (dp[i-1][j],dp[i][j-1]);
                }
                if(dp[i][j]>max){
                    max=dp[i][j];
                    start=i;
                }
            }
        }
        printf("%d\n",max);
        for(int i=start-max;i<=start-1;i++)printf("%c",s1[i]);
        printf("\n");
    }

    return 0;
}

这是为啥??

登录查看完整内容


登录后发布评论

1 条评论
kbgimf
2024年6月25日 10:47

因为满足代码条件的可以是:a非连续lcs == b非连续lcs ;    a非连续lcs == b连续lcs ;   a连续lcs == b非连续lcs ;  a连续lcs == b连续lcs。而这题只需要第四种的答案,算出来的答案确是这四种的最大值,所以只能匹配33%的答案。

赞(2)