UVa 10192

From Algorithmist

Contents 1 10192 - Vacation 2 Summary 3 Explanation 4 Input 5 Output

[edit] 10192 - Vacation

• http://acm.uva.es/p/v101/10192.html

[edit] Summary

This might at first seems like a Graph Theory problem, but it is actually a simple Longest Common Subsequence (Dynamic Programming) problem.

[edit] Explanation

This is a simple Longest Common Subsequence (Dynamic Programming) problem, since this is the trip that would preserve the longest order of either recommendation.

[edit] Input

abcd
acdb
abcd
dacb
#

[edit] Output

Case #1: you can visit at most 3 cities.
Case #2: you can visit at most 2 cities.