解題區/解題區 - Zerojudge

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;
}