problem

博客是一個能非常方便記錄自己學習歷程的工具，而當你的博客內(nèi)容非常多的時候，僅僅使用標簽和分類已經(jīng)不足以讓你快速定位到要找的博文。
這時，就需要一個搜索引擎來讓你更快定位到目標博文。

搜索引擎的基本原理就是計算每一個文章與搜索詞的相似程度，按照相似程度從大到小顯示出來。
經(jīng)過復雜的代碼計算，我們終于解決了字符編碼、拋棄冗雜信息的工作，生成了一個每篇文章的摘要信息。現(xiàn)在給你一些關鍵詞，你能找到最符合要求的文章么？
對于文章的匹配程度定義如下：
如果我們將搜索詞去除幾個單詞，剩余的單詞按順序組成一個搜索序列，并且這個序列在摘要中出現(xiàn)了（可以不連續(xù)），那么我們就稱這個搜索序列與該文章是匹配的。
我們自然希望與該文章匹配的搜索序列越長越好，所以搜索詞與文章的匹配程度就是上述搜索序列的最長長度

Input

第一行為數(shù)據(jù)組數(shù)T（1<=T<=10）
接下來一行為關鍵詞個數(shù)n（1<=n<=100）
緊接著一行是n個英語單詞
下面一行是文章個數(shù)m（1<=m<=100）
接下來m行每行以一個整數(shù)length開頭，表示這篇文章的摘要單詞數(shù)（1<=length<=100）
數(shù)據(jù)保證對于所有關鍵單詞和摘要單詞不超過10個字符，并且只包括小寫英語字母

Output

輸出最符合要求的文章序號(從1開始計數(shù))
如果最符合要求的文章不唯一，輸出序號最小的

Input

1
3
dp search better
3
4 dp is very useful
9 use dp and you can search it in there
6 do better in search with dp

Output

2

Limitation

1s 256MB

Hint

搜索詞為dp、search、better
而文章摘要為dp is very useful、use dp and you can search it in there、do better in search with dp
對于第一篇文章摘要：最長的在文章摘要中出現(xiàn)的搜索詞序列是dp，所以匹配程度是1
對于第二篇文章摘要：最長的在文章摘要中出現(xiàn)的搜索詞序列是dp search，所以匹配程度是2
對于第三篇文章摘要：最長的在文章摘要中出現(xiàn)的搜索詞序列是search或者better或者dp，所以匹配程度是1

傳送門傳送門傳送門傳送門

思路

裸的LCS，本菜比賽時沒有看出來，亂搞沒搞出來

關于LCS：點擊打開鏈接

代碼示例

#include<bits/stdc++.h> using namespace std;const int maxn=110;int n;//摘要詞數(shù)struct w{int num;//單詞數(shù)int ans;//匹配數(shù)vector<string> G;//這個文章的單詞 }wen[maxn];//每一篇文章vector<string> xiang;//待搜索int dp[maxn][maxn];//dp[len][len]表示兩個序列的公共數(shù)量int solve(int loc) {int len1=n;int len2=wen[loc].num;int i,j;for(int i=0;i<=len1;++i) dp[i][0]=0;//無公共子序列for(int i=0;i<=len2;++i) dp[0][i]=0;for(int i=0;i<len1;++i)for(j=0;j<len2;++j){if(xiang[i]==wen[loc].G[j]) dp[i+1][j+1]=dp[i][j]+1;else{dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);}}return dp[len1][len2]; }int main() {ios::sync_with_stdio(false);int t,m;//n為待搜索cin>>t;while(t--){//注意初始化memset(dp,0,sizeof(dp));xiang.clear();for(int i=0;i<=maxn;++i){wen[i].G.clear();}cin>>n;for(int i=0;i<n;++i){string tp;cin>>tp;xiang.push_back(tp);}cin>>m;string tp;int ans=0;int maxx=0;for(int i=0;i<m;++i){cin>>wen[i].num;for(int j=0;j<wen[i].num;++j){cin>>tp;wen[i].G.push_back(tp);}if(solve(i)>maxx){ans=i;maxx=solve(i);}}cout<<ans+1<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的17AHU排位赛3 C题 (LCS)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。