a374. 5. 股票趨勢

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

在限制若選用某個字母下,與前一個所選字母的間距不能大於某個特定值,請問 GLCS 長度為何?

Sample Input

1
2
3
4
5
6
7
8
ACBDCAA ADDBCDBAC
2
$
A 2 B 0 C 3 D 0 $
ACBDCAA ADDBCDBAC
1
C 4 A 6 $

Sample Output

1
2
4 3
4

Solution

明顯地,從一般的 LCS 變化,假設間距都是無窮大,則退化成一般的 LCS,那 LCS 也可以寫成以下方案

$$T[i, j] := \left\{\begin{matrix} \textit{undefined} & A[i] \neq B[j] \\ max \;(T[a, b])+1 & A[i] = B[j], a < i, b < j \end{matrix}\right.$$

從改寫過的 LCS 方案可以看出算法複雜度最慘會到 $O(N^4)$,事實上只有 $O(R N^2)$,其中 $R$ 表示字符匹配的數量。

由於要改寫成每一個字元都有其限制,則 GLCS 會變成以下遞迴公式

$$T[i, j] := \left\{\begin{matrix} \textit{undefined} & A[i] \neq B[j] \\ max \;(T[a, b])+1 & A[i] = B[j], i - K - 1 \le a < i, j - K - 1 \le b < j \end{matrix}\right.$$

可以標準的 RMQ 區間極值查找,但麻煩地方在於處於二維上的極值查找,可以套用線段樹來完成樹套樹達到二維效果。使用 zkw 式只是查找常數比較小,但記憶體會比較大,而基本線段樹的空間開銷是 $4 N^2$。接下來就要完成單點更新、區域極值查找。

時間複雜度 $O(N^2 + R \log^2 N)$。若要更快,請參照論文那樣處理。

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
class D2RMQ {
public:
struct Node {
short mxv;
};
struct D2Tree {
Node subtree[2048];
} d2tree[2048];
int Mmain, Msub;
short ansMax;
void init(int n, int m) {
for (Mmain = 1; Mmain < n+2; Mmain <<= 1);
for (Msub = 1; Msub < m+2; Msub <<= 1);
build();
}
void build() {
for (int i = (Mmain<<1)-1; i > 0; i--)
sub_build(i);
}
void modify(int x, int y, int val) {
static int s, t;
d2tree[x+Mmain].subtree[y+Msub].mxv = val;
t = x+Mmain;
for (s = (y+Msub)>>1; s > 0; s >>= 1)
d2tree[t].subtree[s].mxv = max(d2tree[t].subtree[s<<1].mxv, d2tree[t].subtree[s<<1|1].mxv);
for (s = (x+Mmain)>>1; s > 0; s >>= 1)
sub_modify(s, y);
}
void query(int lr, int rr, int lc, int rc) {
static int s, t;
ansMax = 0;
if (lr <= rr && lc <= rc)
for (s = lr+Mmain-1, t = rr+Mmain+1; (s^t) != 1;) {
if (~s&1)
sub_query(s^1, lc, rc);
if (t&1)
sub_query(t^1, lc, rc);
s >>= 1, t >>= 1;
}
}
private:
void sub_build(int k) {
memset(d2tree[k].subtree, 0, sizeof(Node) * Msub * 2);
// for (int i = (Msub<<1)-1; i > 0; i--)
// d2tree[k].subtree[i].mxv = 0;
}
void sub_modify(int k, int y) {
for (int s = y+Msub; s > 0; s >>= 1)
d2tree[k].subtree[s].mxv = max(d2tree[k<<1].subtree[s].mxv, d2tree[k<<1|1].subtree[s].mxv);
}
void sub_query(int k, int lc, int rc) {
static int s, t;
for (s = lc+Msub-1, t = rc+Msub+1; (s^t) != 1;) {
if (~s&1)
ansMax = max(ansMax, d2tree[k].subtree[s^1].mxv);
if (t&1)
ansMax = max(ansMax, d2tree[k].subtree[t^1].mxv);
s >>= 1, t >>= 1;
}
}
} tool;
char s1[1024], s2[1024];
char ss[32767];
int main() {
int testcase, cases = 0;
while (scanf("%s %s", s1+1, s2+1) == 2) {
scanf("%d", &testcase);
int n = strlen(s1+1), m = strlen(s2+1);
int gap[256] = {};
while (testcase--) {
int GLCS = 0;
for (int i = 0; i < 256; i++)
gap[i] = 0x3f3f3f3f;
while (scanf("%s", ss) == 1 && ss[0] != '$')
scanf("%d", &gap[ss[0]]);
tool.init(n, m);
int K, lx, ly, rx, ry, dp;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s1[i] == s2[j]) {
K = gap[s1[i]];
lx = max(i-K-1, 1), ly = max(j-K-1, 1);
rx = i-1, ry = j-1;
tool.query(lx, rx, ly, ry);
dp = tool.ansMax+1;
tool.modify(i, j, dp);
GLCS = max(GLCS, dp);
}
}
}
printf("%d", GLCS);
if (testcase)
printf(" ");
}
puts("");
}
return 0;
}