# UVa 10131

Jump to navigation
Jump to 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 . 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