Vijos1028. 魔族密碼
來源：程序員人生 發布時間：2014-10-08 08:00:00 閱讀次數：1994次
試題請參見: 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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
