Codeforces 156A：DP 求最長特定子序列

題目描述

給定數列 a[1..n]，求最長子序列滿足：相鄰元素在原數列中位置差為 1，且值相同？實際題目為：對每個值壓縮編號，dp[i][j] 表示以第 i 個元素結尾、前一元素為第 j 號值的最長子序列長度。轉移：dp[i][j] = dp[last[j]][id[a[i]]] + 1。其中 last[v] 為值 v 最後出現位置，id[x] 為值 x 的壓縮編號。

核心代碼邏輯

// 壓縮值域
map id;
int cnt = 0;
for (int i=1;i<=n;++i) if (!id.count(a[i])) id[a[i]] = ++cnt;

// DP
vector> dp(n+1, vector(cnt+1, 1));
vector last(cnt+1, 0);
int ans = 1;
last[id[a[1]]] = 1;
for (int i=2;i<=n;++i) {
    for (int j=1;j<=cnt;++j) {
        dp[i][j] = dp[last[j]][id[a[i]]] + 1;
        ans = max(ans, (int)dp[i][j]);
    }
    last[id[a[i]]] = i;
}
printf("%d\n", ans);

關鍵點

• 值域壓縮將狀態數從值大小降為不同值個數。
• last[] 記錄每值最近位置，實現 O(1) 轉移。
• 時間 O(n × distinct_values)，空間 O(n × distinct_values) 可優化為滾動數組。