HDU 4749 Parade Show：連續子序列模式匹配的貪心模擬

題目大意

有 n 名學生按編號 1..n 排成一排，身高分為 k 級（1≤k≤25）。給定最佳觀賞模組 a[1..m]，需從隊列中選取若干個長度為 m 的連續子隊列，重新編號 1..m 後，若任意兩位學生的身高大小關係與 a 中對應位置一致，則稱該隊列「設計良好」。每生只能屬於一個隊列或不被選。求最多能組成多少個設計良好的隊列。

解法

因 k ≤ 25，可將身高關係轉化為相對大小模式。對每個長度為 m 的滑動窗口，檢查其相對大小關係是否與 a 完全一致。若一致，計數加一，並跳過該窗口（因學生不可重用）；否則向右滑動一位。時間 O(n·m)，n≤10⁵, m≤n，但實測通過。

關鍵代碼

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 100000 + 10
int num[MAXN], mark[MAXN];
int main() {
    int n, m, k, i, j, K;
    while (~scanf("%d%d%d", &n, &m, &k)) {
        memset(num, 0, sizeof(num));
        memset(mark, 0, sizeof(mark));
        for (i = 0; i < n; i++) scanf("%d", &num[i]);
        for (i = 0; i < m; i++) scanf("%d", &mark[i]);
        int ans = 0;
        for (i = 0; i <= n - m; ) {
            int count = 0;
            for (j = 0, K = i; j < m - 1; j++, K++) {
                if ((mark[j] < mark[j + 1] && num[K] < num[K + 1]) ||
                    (mark[j] == mark[j + 1] && num[K] == num[K + 1]) ||
                    (mark[j] > mark[j + 1] && num[K] > num[K + 1]))
                    count++;
            }
            if (count == m - 1) { ans++; i += m; }
            else i++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

總結

本題利用身高關係的傳遞性，僅需比較相鄰位置的大小關係即可判斷整個序列是否同構，配合貪心跳過已用學生，實現線性掃描。