文章

82

粉丝

344

获赞

28

访问

698.1k

头像
LCS
P1293 上海交通大学机试题
发布于2021年3月5日 14:47
阅读数 7.8k

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <string>
using namespace std;

//转移方程(二维)
//f[i][j]代表第一个字符串前i个第二个字符串前j个的情况
//f[i][j]:
//f[i-1][j-1],f[i-1][j],f[i][j-1],f[i-1][j-1]+1四种状态
//i不选j不选   i不选j选  i选j不选   i选j选
//状态四一定大于状态一,直接忽略状态一
// if(a[i-1]==b[j-1]) f[i][j]=f[i-1][j-1]+1;
// if(a[i-1]!=b[j-1])  f[i][j]=max(f[i-1][j],f[i][j-1]);
//f数组从1开始  ab串从0开始 因此要用a[i-1] b[j-1]
const int maxn=1001;
char a[maxn],b[maxn];
int f[maxn][maxn];
int main(){
    while(scanf("%s%s",a,b)!=EOF){
        int n=strlen(a);
        int m=strlen(b);
        memset(f,0,sizeof(f));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(a[i-1]==b[j-1]){
        &...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发