หาต้นทุนต่ำสุดเลือก k Unique Subsequences จากสตริงใน C++

บทนำ

ในบทช่วยสอนนี้ เราจะเลือก k unique subsequences จากสตริง s เพื่อให้ ต้นทุนรวมน้อยที่สุด

กฎต้นทุน

ต้นทุนของ subsequence = len(s) - len(subsequence)
คือ ยิ่ง subsequence สั้น ยิ่งแพง (เพราะตัดทิ้งมาก)

ตัวอย่าง

s = "pqrs", k = 4
Output: 3
Subsequences: "pqrs" (cost 0), "pqr" (cost 1), "pqs" (cost 1), "prs" (cost 1) → รวม 3

อัลกอริทึม: DP นับ Unique Subsequences ตามความยาว

dp[i][j] = จำนวน unique subsequences ความยาว j จาก prefix s[0..i-1]
Transition: dp[i+1][j] = dp[i][j] + dp[i][j-1] (ไม่เอา/เอา s[i])
แต่ต้องลบ subsequences ที่ซ้ำ → ใช้ last[c] เก็บ index ล่าสุดของตัวอักษร c

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

int solve(string s, int k) {
    int n = s.size();
    vector> dp(n + 1, vector(n + 1, 0));
    unordered_map last;
    
    dp[0][0] = 1;
    
    for (int i = 0; i < n; i++) {
        dp[i + 1][0] = 1;
        for (int j = i + 1; j >= 1; j--) {
            dp[i + 1][j] = dp[i][j] + dp[i][j - 1];
        }
        if (last.find(s[i]) != last.end()) {
            for (int j = 0; j <= last[s[i]]; j++) {
                dp[i + 1][j + 1] -= dp[last[s[i]]][j];
            }
        }
        last[s[i]] = i;
    }
    
    int cost = 0;
    for (int i = n; i >= 0; i--) {
        int val = min(k, dp[n][i]);
        cost += val * (n - i);
        k -= dp[n][i];
        if (k <= 0) break;
    }
    
    if (k <= 0) return cost;
    return -1;
}

int main() {
    cout << solve("pqrs", 4) << endl;
    return 0;
}

ผลลัพธ์

คำอธิบาย

DP นับ unique subsequences ทุกความยาว
Greedy: เลือก subsequence ยาวที่สุดก่อน (cost ต่ำสุด) จนครบ k
i=n (ความยาวเต็ม) → cost 0, i=n-1 → cost 1, ฯลฯ

สรุป

DP + Greedy หา k unique subsequences ต้นทุนต่ำสุด Cost = n - length เลือกยาวก่อน หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ