Codeforces Round #309 (Div. 1) A. Kyoya and Colored Balls

原题:http://codeforces.com/contest/553/problem/A


题目大意: k个颜色, n个球, 球之间没区别. 问怎么放能至少让一个i个颜色的球排在i+1的颜色的球的前边.


分析:这题目看起来是很拗口, 我看着发愣了一会儿才明白. 颜色是有顺序的.第i+1颜色的前边至少要有一个i颜色的球, 这个i不是固定的. 1<=i<=k-1, 所以题目也可以解释成,至少一组球是有序的, 这个有序不一定是连续的球. 因为i表示的颜色是个范围, 所以要用dp来做, 假设i = 1, 这时候就一种颜色, 因为球和球之间无区别, 所以答案是1. i = 2的时候, 因为要保持以上的条件, 所以我们选一个颜色为2的球,放到最后, 然后其他的无所谓.

IMG_0538IMG_0539(点一下,有清楚的图)