POJ 1952 Buy Low, Buy Lower：最長遞減子序列計數與去重詳解

問題背景

POJ 1952「Buy Low, Buy Lower」要求在給定序列中找出最長遞減子序列（LDS）的長度，並計算有多少個不同的最長遞減子序列。關鍵難點在於去重：當序列中出現相同數值且能形成相同長度的子序列時，必須避免重複計數。

核心思路

採用動態規劃（DP）記錄以每個位置結尾的最長遞減子序列長度 tbl[i] 及其數量 C[i]。為了去重，利用以下觀察：若前面已出現相同數值 arr[j] == arr[i] 且 tbl[j] == tbl[i]，則以 i 結尾的子序列中，那些已經被 j 計數過的部分應扣除。具體做法是：在計算完 C[i] 後，遍歷 j < i，若 arr[j] == arr[i] 且 tbl[j] == tbl[i]，則 C[i] -= C[j]。

經典去重案例

• 9 8 9 8 2：兩個 9 和兩個 8 會產生重複子序列，需正確扣除。
• 10 5 12 5 3：中間的 5 與前面的 5 形成相同長度的遞減子序列，去重邏輯同樣適用。

複雜度與代碼實現

本題採用 O(N^2) DP，N ≤ 5000 可接受。若不需計數，可用 O(N log N) 的 LIS 變體，但計數與去重較難在該框架下實現。

#include <stdio.h>
#include <vector>
#include <string.h>
#include <iostream>
#include <string>
#include <limits.h>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
const int MAX_N = 5001;
int arr[MAX_N], N, tbl[MAX_N], C[MAX_N];

void getLongest(int &len, int &n) {
    memset(tbl, 0, sizeof(int) * (N+1));
    memset(C, 0, sizeof(int) * (N+1));
    tbl[0] = 1; C[0] = 1;
    for (int i = 1; i < N; i++) {
        tbl[i] = 1;
        for (int j = 0; j < i; j++) {
            if (tbl[j] == -1) continue;
            if (arr[j] > arr[i] && tbl[i] < tbl[j]+1) {
                tbl[i] = tbl[j]+1;
            }
        }
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[i] && tbl[i] == tbl[j]+1) {
                C[i] += C[j];
            }
        }
        if (C[i] == 0) C[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr[j] == arr[i] && tbl[j] == tbl[i]) C[i] -= C[j];
        }
    }
    len = INT_MIN;
    for (int i = 0; i < N; i++) len = max(len, tbl[i]);
    n = 0;
    for (int i = 0; i < N; i++) if (tbl[i] == len) n += C[i];
}

int main() {
    while (scanf("%d", &N) != EOF) {
        for (int i = 0; i < N; i++) scanf("%d", arr + i);
        int len, n; getLongest(len, n);
        printf("%d %d\n", len, n);
    }
    return 0;
}