Vijos1028. 魔族密碼

試題請參見: https://vijos.org/p/1028

題目概述

風之子剛走進他的考場, 就……

花花: 當當當當~~偶是魅力女皇——花花!!^^(華麗出場, 禮炮, 鮮花)

風之子: 我嘔……(殺死人的眼神)快說題目!否則……-_-###

花花: ……咦~~好冷~~我們現在要解決的是魔族的密碼問題(自我陶醉: 搞不好魔族裡面還會有人用密碼給我和菜蟲寫情書咧, 哦活活, 當然是給我的比較多拉*^_^*). 魔族現在使用一種新型的密碼系統. 每一個密碼都是一個給定的僅包含小寫字母的英文單詞表, 每個單詞至少包含1個字母, 至多75個字母. 如果在一個由一個詞或多個詞組成的表中, 除了最後一個以外, 每個單詞都被其後的一個單詞所包含, 即前一個單詞是後一個單詞的字首, 則稱詞表為一個詞鍊. 例如下面單詞組成了一個詞鍊: 

i

int

integer

但下面的單詞不組成詞鍊: 

integer

intern

現在你要做的就是在一個給定的單詞表中取出一些詞, 組成最長的詞鍊, 就是包含單詞數最多的詞鍊. 将它的單詞數統計出來, 就得到密碼了. 

風之子: 密碼就是最長詞鍊所包括的單詞數啊……

輸入

第一行為單詞表中的單詞數N(1<=N<=2000), 下面每一行有一個單詞, 按字典順序排列, 中間沒有重複的單詞.

輸出

在第一行輸出密碼

解題思路

這道題是最長不下降子序列. 比如一個序列{ 3, 5, 6, 2, 8 }, 則最長不下降子序列為{ 3, 5, 6, 8 }.

那麼如何求這個序列呢? 這個問題可以轉換為, 求f(i) = max{ f(j) } + 1. (其中f(j)為前j個數中的最長不下降子序列)

我們需要一個數組length[], 記錄1~n個元素的最長不下降子序列的值. 

對于第i個元素, length[i] = max{ length[j] } + 1( 0 <= j < i ), 且滿足 words[j] 是 words[i] 的子序列(words[]是用于儲存單詞鍊的數組).

遇到的問題

難得這麼順利, 沒有遇到什麼問題, 連O(n^2)的代碼也能AC.

源代碼

#include <iostream>
#include <fstream>
#include <string>

bool compareString(const std::string& str1, const std::string& str2) {
    size_t i = 0, j = 0;
    for ( ; i < str1.size() && j < str2.size(); ++ i, ++ j ) {
        if ( str1[i] != str2[j] ) {
            break;
        }
    }
    return (i == str1.size() || j == str2.size());
}

int main() {
    using std::cin;
    // std::ifstream cin;
    // cin.open("input.txt");

    const int SIZE = 2000;
    int n = 0;
    std::string words[SIZE];

    // Input
    cin >> n;
    for ( int i = 0; i < n; ++ i ) {
        cin >> words[i];
    }

    // Processing
    int length[SIZE] = {0};
    for ( int i = 0; i < n; ++ i ) {
        length[i] = 1;
        for ( int j = 0; j < i; ++ j ) {
            if ( compareString(words[i], words[j]) && length[j] <= length[i]) {
                length[i] = length[j] + 1;
            }
        }
    }

    // Output
    int maxLength = 0;
    for ( int i = 0; i < n; ++ i ) {
        if ( length[i] > maxLength ) {
            maxLength = length[i];
        }
    }
    std::cout << maxLength << std::endl;

    return 0;
}