目录

  1. 引言
  2. BZOJ 3304: [Shoi2005]带限制的最长公共子序列
    1. Description
    2. Input
    3. Output
    4. Sample Input
    5. Sample Output
    6. HINT
    7. 题目分析
    8. 代码

引言

BZOJ 3304: [Shoi2005]带限制的最长公共子序列 题解

BZOJ 3304: [Shoi2005]带限制的最长公共子序列

  • Time Limit: 10 Sec

  • Memory Limit: 128 MB

Description

Input

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

Output

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

Sample Input

helloworld

hellxebore

xr

Sample Output

5

HINT

w=hxeor

本题要求找出的W首先是X与Y的公共子序列并且包含Z,然后才是满足这些条件的

字符串里面找最长的。

题目分析

MDZZ,吃饭的时候都在想这道题,结果一看题解,$O(n ^ 3)$可过?!

真是f**k

直接记录三个串各自的匹配位置滚动一下就好

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 515
#define INF 2000000005
#define rep(i, l, r) for (register int i = l; i <= r; i++)
#define per(i, r, l) for (register int i = r; i >= l; i--)
#define gc() ((p1 == p2 && (p2 = (p1 = buffer) + fread(buffer, 1, maxn, stdin), p1 == p2)) ? EOF : *p1++)
using namespace std;
char *p1, *p2;
char buffer[maxn];
template <class T> void read(T& x){
char ch = gc(); x = 0; bool f = 1;
while (!('0' <= ch && ch <= '9') && ch != '-') ch = gc();
if (ch == '-') f = 0, ch = gc();
while ('0' <= ch && ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = gc();
if (!f) x = -x;
}
int n, m, k;
char a[maxn], b[maxn], c[maxn];
int dp[maxn][maxn][2];
int main(){
#ifndef ONLINE_JUDGE
freopen("lcs.in", "r", stdin);
#endif
scanf("%s%s%s", a + 1, b + 1, c + 1);
n = strlen(a + 1), m = strlen(b + 1), k = strlen(c + 1);
int d = 0;
per(l, k + 1, 1) {
if (l != k + 1){
rep(i, 1, n + 1) dp[i][m + 1][d] = -INF;
rep(i, 1, m + 1) dp[n + 1][i][d] = -INF;
}
per(i, n, 1) per(j, m, 1) {
if (a[i] == b[j]){
if (a[i] == c[l]) dp[i][j][d] = max(dp[i + 1][j + 1][d ^ 1], dp[i + 1][j + 1][d]) + 1;
else dp[i][j][d] = dp[i + 1][j + 1][d] + 1;
}
else dp[i][j][d] = max(dp[i + 1][j][d], dp[i][j + 1][d]);
}
d ^= 1;
}
if (dp[1][1][d ^ 1] > 0) printf("%d", dp[1][1][d ^ 1]);
else printf("NO SOLUTION");
return 0;
}