UVa 10131

From Algorithmist
Jump to: navigation, search

10131 - Is Bigger Smarter[edit]

Summary[edit]

A standard Dynamic Programming (Longest Increasing Subsequence) problem.

Explanation[edit]

This can also be viewed as a Graph Theory problem, as the Longest Increasing Subsequence problem reduces to finding the longest path in a Directed Acyclic Graph. Therefore, this problem can be solved in O(nlogn). Using each elephant as a vertex, an edge can be drawn from a bigger, smarter (strictly) elephant to one that is less so.

Input[edit]

6008 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900

Output[edit]

4
4
5
9
7

Solutions[edit]