Your backyard has been overrun by preposterously large hippos, and they are eating the tulips!
You have a line of N tulips, labelled from 1 to N. There are H hippos standing next to different tulips ...and they are already eating them! If you don't act fast, they will eat all the tulips in your garden.
You have enough plywood to build up to F fences. Each fence will be built between two tulips that are next to each other. Hippos cannot go through fences (or over them, or under them, or around them).
Once you have built your fences, the hippos will roam back and forth along the line of tulips, eating all the tulips they can reach without crossing your fences. What is the greatest number of tulips you can save?
Your program should read from the file hippoin.txt.
Your program should write to the file hippoout.txt. Your output file should contain one line with one integer: the greatest number of tulips you can save.
9 3 3 2 5 7
7 2 1 1 7
In the first sample case, as illustrated above, if we put a fence between tulips 2 and 3, between tulips 4 and 5 and between tulips 7 and 8, no hippo will be able to reach tulips 3, 4, 8 or 9. There is no placement of fences that will save more tulips, so 4 is the correct answer.
In the second sample case, no matter where you place the one fence you will not be able to save any tulips.
To evaluate your solution, the judges will run your program against several different input files. All of these files will adhere to the following bounds:
As some of the test cases will be quite large, you may need to think about how well your solution scales for larger input values. However, not all the cases will be large. In particular: