列表

详情


NC20398. [SHOI2005]带限制的最长公共子序列

描述

输入描述

输入共三行,每行为长度不超过500的,小写字母组成的非空字符串按顺序分别表示x,y,z

输出描述

如存在满足条件的N,输出W的长度,否则输出 NO SOLUTION

示例1

输入:

helloworld
hellxebore
xr

输出:

5

原站题解

import java.util.Scanner;
public class Main {
public static void main(String[] arg) {
Scanner scanner = new Scanner(System.in);
// todo
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

C++(clang++ 11.0.1) 解法, 执行用时: 131ms, 内存消耗: 2436K, 提交时间: 2022-10-01 21:54:34

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 504
#define inf -10000
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int f[2][N][N];
char A[N],B[N],C[N];
void getmax(int &a,int b)
{
if(b>a) a=b;
}
int main()
{
// setIO("input");
int x,y,z,i,j,k;
scanf("%s%s%s",A+1,B+1,C+1);
x=strlen(A+1);
y=strlen(B+1);
z=strlen(C+1);
memset(f,-0x3f,sizeof(f));
f[0][0][0]=0;
int ans=0;
for(i=0;i<=x;++i)
{
int now=i%2;
f[now][0][0]=0;
for(j=0;j<=y;++j)
{
for(k=0;k<=min(z,min(i,j));++k)
{
if(i+j+k) f[now][j][k]=inf;
if(i) getmax(f[now][j][k],f[now^1][j][k]);
if(j) getmax(f[now][j][k],f[now][j-1][k]);
if(i&&j&&A[i]==B[j]) getmax(f[now][j][k],f[now^1][j-1][k]+(A[i]==B[j]));
if(i&&j&&k&&(A[i]==B[j]&&B[j]==C[k])) getmax(f[now][j][k],f[now^1][j-1][k-1]+1);
}
}
}
if(max(f[0][y][z],f[1][y][z])<z) printf("NO SOLUTION\n");
else printf("%d\n",max(f[0][y][z],f[1][y][z]));
return 0;
}

上一题