import java.util.Scanner;
public class Main {
public static void main(String[] arg) {
Scanner scanner = new Scanner(System.in);
// todo
}
}
NC20398. [SHOI2005]带限制的最长公共子序列
描述
输入描述
输入共三行,每行为长度不超过500的,小写字母组成的非空字符串按顺序分别表示x,y,z
输出描述
如存在满足条件的N,输出W的长度,否则输出 NO SOLUTION
示例1
输入:
helloworld hellxebore xr
输出:
5
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;}