poj3276专题

《挑战程序设计竞赛》3.2.2 常用技巧-反转 POJ3276 3279 3185 1222

POJ3276 http://poj.org/problem?id=3276 题意 N头牛排成一列1<=N<=5000。每头牛或者向前(表示为F)或者向后(表示为B)。为了让所有牛都面向前方,农夫每次可以将K头连续的牛转向1<=K<=N,求操作的最少次数M和对应的最小K。 思路 所有情况穷举O(2^N)肯定超时。 顺序考虑每头牛的反转方向能不能行呢?因为想改变一头牛的方向就必定影响k头