UVa 531 Compromise

📅 2026/7/4 4:29:34 👁️ 次浏览

题目描述题目要求找出两个文本的最长公共子序列LCSLongest Common Subsequence\texttt{LCSLongest Common Subsequence}LCSLongest Common Subsequence文本由若干单词组成单词之间用空白分隔以#结尾。输出任意一个最长公共子序列单词序列。输入格式输入包含多个测试用例。每个测试用例包含两段文本每段文本由若干单词组成以单独一行的#结束。输入以文件结束符EOF\texttt{EOF}EOF终止。输出格式对于每个测试用例输出一行包含最长公共子序列中的单词单词之间用空格分隔。样例输入die einkommen der landwirte sind fuer die abgeordneten ein buch mit sieben siegeln um dem abzuhelfen mussen dringend alle subventionsgesetze verbessert werden # die steuern auf vermoegen und einkommen sollten nach meinung der abgeordneten nachdrucklich erhoben werden dazu mussen die kontrollbefugnisse der finanzbehoerden dringend verbessert werden #输出die einkommen der abgeordneten mussen dringend verbessert werden题目分析本题的核心是求解单词序列的最长公共子序列并输出子序列本身。动态规划设dp[i][j]\textit{dp}[i][j]dp[i][j]表示第一个文本的前iii个单词和第二个文本的前jjj个单词的LCS\texttt{LCS}LCS长度。转移方程若word1[i]word2[j]\textit{word1}[i] \textit{word2}[j]word1[i]word2[j]则dp[i][j]dp[i−1][j−1]1\textit{dp}[i][j] \textit{dp}[i-1][j-1] 1dp[i][j]dp[i−1][j−1]1。否则dp[i][j]max⁡(dp[i−1][j],dp[i][j−1])\textit{dp}[i][j] \max(\textit{dp}[i-1][j], \textit{dp}[i][j-1])dp[i][j]max(dp[i−1][j],dp[i][j−1])。同时记录路径方向以便回溯输出单词。输出从(n,m)(n, m)(n,m)回溯到(0,0)(0, 0)(0,0)当遇到相等单词时将其加入结果列表最后反转输出。复杂度分析单词数n,m≤100n, m \le 100n,m≤100时间复杂度O(n×m)O(n \times m)O(n×m)空间复杂度O(n×m)O(n \times m)O(n×m)。代码实现// Compromise// UVa ID: 531// Verdict: Accepted// Submission Date: 2016-08-11// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string first[110],second[110];intcommom[110][110][2]{0};while(true){string word;intfirst_count1;while(cinword){if(word#)break;first[first_count]word;}intsecond_count1;while(cinword){if(word#)break;second[second_count]word;}if(first_count1)break;memset(commom,0,sizeof(commom));for(inti1;ifirst_count;i)for(intj1;jsecond_count;j){if(first[i]second[j](commom[i-1][j-1][0]1)commom[i][j][0]){commom[i][j][0]commom[i-1][j-1][0]1;commom[i][j][1]1;}if(commom[i-1][j][0]commom[i][j][0]){commom[i][j][0]commom[i-1][j][0];commom[i][j][1]2;}if(commom[i][j-1][0]commom[i][j][0]){commom[i][j][0]commom[i][j-1][0];commom[i][j][1]3;}}vectorstringwords;intendifirst_count-1,endjsecond_count-1;while(commom[endi][endj][1]0){if(commom[endi][endj][1]1){words.push_back(first[endi]);endi-1,endj-1;}elseif(commom[endi][endj][1]2)endi-1;elseif(commom[endi][endj][1]3)endj-1;}reverse(words.begin(),words.end());for(inti0;iwords.size();i){if(i0)cout ;coutwords[i];}cout\n;}return0;}

相关新闻