1003-F. Abbreviation

2021-03-22 14:13:27 +0800 CST Tags: dp, sequence

出處：https://codeforces.com/contest/1003/problem/F
提交：https://codeforces.com/contest/1003/submission/110702340

問題：給定 $n\in[1,300]$ 個用單空白分隔的單字 $w[i]$，保證文本全長 (含空白) 不超過 $10^5$，請問該文本經過「至多一次縮寫」之後的最短長度為何？所謂「縮寫」的意思是，挑出至少兩個以上匹配、不重疊的連續單字區間，再讓每個區間都縮減成一個「只取各個單字的第一個字母，並且刪減掉中間所有空格的新單字」。所謂兩段連續單字區間匹配的意思是，兩區間彼此之間對應位置的單字皆相同，例如文本 “a ab a a b ab a a b c” 裡面第 2-5 區間的 “ab a a b” 和第 6-9 區間的 “ab a a b” 就是一組匹配的區間。

解法：第一時間想得到的解法，如果先不考慮 DP 怎麼設計遞迴式的話，應該是先決定一個基底區間 seg，之後往後查找最多有幾個彼此互不重疊而且與 seg 匹配的區間 [1]，計算暫時解，接著再嘗試下一個基底區間，一樣會得到另一個暫時解，重複這個流程，那麼最後得到的最小暫時解就是我們要的。那麼現在最重要的問題就是，給定一個 seg，如何快速地在往後的序列中找到最多與 seg 匹配的區間？可能會有大大想使用 KMP 技巧，這邊應該也是可行，只可惜這個技巧我不甚熟悉，而且在競程的時間壓力下也應該選擇相對好理解/實作的方式，於是這邊採用一般的 DP 技巧。參考解答的作法還蠻聰明的，我可能沒辦法自己想到，它定義 DP[i][j] 是為區間 $w[i:n]$ 與 $w[j:n]$ 以「$w[i]=w[j]$」為首的最長匹配子區間長度，如果 $w[i]\ne w[j]$ 則長度為 0，填表順序可以每次固定 i 和 j 的差距再由後往前 bottom up 得到，在此便不贅述。有了這個表之後，我們就能快速地得到想要的答案，舉例來說，我希望在 $w[i:n]$ 尋找以 $w[i:i+(s-1)]$ 為基底區間的答案，那麼我其實可以每次觀察 DP[i][j] 的值，j 從 i+s 起跳，如果它不小於 s，代表我可以立刻再取出一段長度 s 的匹配區間並把 j 更新為 j+s；如果它小於 s，代表我無法取出以 $w[j]$ 為首的匹配區間，那麼 j 就更新為 j+1，並繼續搜尋，過程結束後所有蒐集到的區間就組成最多匹配區間，此時就可以算暫時最佳解。而所有暫時最佳解裡面最小的那個就是我們要的答案！

附註：
[1] 要從一個大區間內找到最多的指定子區間，一般大家認為 greedy 的方式就是從左往右一路掃過去，一遇到符合的子區間就納入答案中，接著再跳往該子區間末尾的下一個字串繼續搜尋，而這個方法其實也是正確的。但證明魔人可能很好奇，如果先暫時略過一個符合的子區間，繼續往下查找，有沒有可能找到更多呢？答案是不會的。簡單證明如下：如果我不放過任何一個機會，假設這樣子是從 $w[i_1:j]$ 的區間找答案；如果我稍稍放過一些機會，假設這樣子是從 $w[i_2:j]$ 的區間找答案，那麼我們便可以說 $i_1\ge i_2$，此時因為我至少可以把 $w[i_2:j]$ 的最優選擇直接平移到 $w[i_1:j]$ 裡面，或者換句話說，$w[i_1:j]$ 的這個區間一定包含 $w[i_2:j]$ 的最優組合，所以吾人可以推得 $w[i_1:j]$ 的最優解數量勢必不小於 $w[i_2:j]$ 的最優解數量的結論。

實作：

 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


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

int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
    int n, maX, sum, totalsum, dp[301][301]={0};
    string w[301]; cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> w[i];
        totalsum += w[i].length();
    }
    for (int d=0; d<=n-1; d++) { // d := difference between two indices
        for (int i=n; i-d>=1; i--) { // i := starting index
            if (w[i-d] == w[i]) {
                if (i+1 > n)
                    dp[i-d][i] = 1;
                else
                    dp[i-d][i] = dp[i-d+1][i+1] + 1;
            }
        }
    } // dp[i][j] denotes the size of the two longest equal segments (intersecting or non-intersecting)
    // starting from w[i] and w[j], where i <= j.
    for (int i=1; i<n; i++) {
        int sum = 0;
        for (int s=1; i+s-1<n; s++) {
            int cnt = 1; sum += w[i+s-1].length(); // we want to find the maximum number of non-intersecting equal segments
            for (int j=i+s; j<=n; j++) { // w[j..j+(s-1)] (for all j >= i) matching w[i..i+(s-1)].
                if (dp[i][j] >= s) {
                    j += s-1;
                    cnt++;
                }
            }
            if (cnt >= 2)
                maX = max(maX, cnt * (sum-1)); // 縮水的長度為該區段可見的單字總長 - 單字數 + (空格數 = 單字數 - 1) = 可見的單字總長 - 1
        }
    }
    cout << totalsum + n-1 - maX;
    return 0;
}

結果： Example image