UVa 10192

From Algorithmist
Jump to navigation Jump to search

10192 - Vacation[edit]

Summary[edit]

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

Explanation[edit]

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

Implementations[edit]

Input[edit]

abcd
acdb
abcd
dacb
#

Output[edit]

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