http://poj.org/problem?id=2250
最长公共子序列LCS 动态规划DP
Compromise
Time Limit:1000MS |
|
Memory Limit:65536K |
|
|
|
|
Special Judge |
Description
In a few months the European Currency Union will become a reality. However, to join the club, the Maastricht criteria must be fulfilled, and this is not a trivial task for the countries (maybe except for Luxembourg). To enforce that Germany will fulfill the criteria, our government has so many wonderful options (raise taxes, sell stocks, revalue the gold reserves,...) that it is really hard to choose what to do.
Therefore the German government requires a program for the following task:
Two politicians each enter their proposal of what to do. The computer then outputs the longest common subsequence of words that occurs in both proposals. As you can see, this is a totally fair compromise (after all, a common sequence of words is something what both people have in mind).
Your country needs this program, so your job is to write it for us.
Input
The input will contain several test cases.
Each test case consists of two texts. Each text is given as a sequence of lower-case words, separated by whitespace, but with no punctuation. Words will be less than 30 characters long. Both texts will contain less than 100 words and will be terminated by a line containing a single '#'.
Input is terminated by end of file.
Output
For each test case, print the longest common subsequence of words occuring in the two texts. If there is more than one such sequence, any one is acceptable. Separate the words by one blank. After the last word, output a newline character.
Sample Input
die einkommen der landwirte
sind fuer die abgeordneten ein buch mit sieben siegeln
um dem abzuhelfen
muessen dringend alle subventionsgesetze verbessert werden
#
die steuern auf vermoegen und einkommen
sollten nach meinung der abgeordneten
nachdruecklich erhoben werden
dazu muessen die kontrollbefugnisse der finanzbehoerden
dringend verbessert werden
#
Sample Output
die einkommen der abgeordneten muessen dringend verbessert werden
改成循环数组,优化后
分享到:
相关推荐
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
3.徐持衡《浅谈几类背包题》 8.徐源盛《对一类动态规划问题的研究》 背包九讲Pack 【专辑】插头DP 【专辑】单调队列+斜率优化的DP ...最长公共子序列和字符串相似度 最大矩阵连乘次数(最小连乘变形)
动态规划DP题解 POJ HDU 动态规划解题报告
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
OJ动态规划DP题目列表 POJ SOJ HDU 动态规划题目
北大POJ初级-动态规划 解题报告+AC代码
PKU Online Judge上面很全面的动态规划试题总结。动态规划是ACM考点中最重要的一大类算法之一,对于工作人员来说,动态规划也是实际开发中...这是POJ上面很多DP题目的总结与深刻分析。利于算法学习,学长给的,在此分享
动态规划DP题解 POJ HDU部分动态规划DP题解
LMS Longest Monotonically Increasing Sequence Algorithm
POJ ACM 1015 Jury Compromise 两种解法 解题报告
动态规划算法poj1088滑雪实验报告 动态规划算法poj1088滑雪实验报告
POJ上的DP分类: 容易: 1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740(博弈), 1742, 1887, 1926(马尔科夫矩阵,求...
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
这是一道很不错的题目,dp解决的经典例子,是学习dp,和练习的好题目。。。。
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
这是黑不来就的poj上的所有dp题目的大型分类 好使好用