Kobolds are rat-like, candle-loving cave folk, digging deep beneath the surface for millennia. Today, they gather together in a queue to explore yet another tunnel in their catacombs!But just before the glorious movement initiates, they have to arrange themselves in non-descending heights. The shortest is always the leader digging small holes, and the followers swelling it. The kobolds are hyperactive; they like to move here and there. To make the arrangement easier, they decide to group themselves into consecutive groups first, then reorder in each group. What's the maximum number of consecutive groups they can be partitioned into, such that after reordering the kobolds in each group in non-descending order, the entire queue is non-descending?For example, given a queue of kobolds of heights [1,3,2,7,4]{[1, 3, 2, 7, 4]}[1,3,2,7,4], we can group them into three consecutive groups , such that after reordering each group, the entire queue can be non-descending.
Kobolds are rat-like, candle-loving cave folk, digging deep beneath the surface for millennia. Today, they gather together in a queue to explore yet another tunnel in their catacombs! But just before the glorious movement initiates, they have to arrange themselves in non-descending heights. The shortest is always the leader digging small holes, and the followers swelling it. The kobolds are hyperactive; they like to move here and there. To make the arrangement easier, they decide to group themselves into consecutive groups first, then reorder in each group. What's the maximum number of consecutive groups they can be partitioned into, such that after reordering the kobolds in each group in non-descending order, the entire queue is non-descending? For example, given a queue of kobolds of heights [1,3,2,7,4]{[1, 3, 2, 7, 4]}[1,3,2,7,4], we can group them into three consecutive groups ([1][3,2][7,4]{[1] [3, 2] [7, 4]}[1][3,2][7,4]), such that after reordering each group, the entire queue can be non-descending.
标签: HBC223805[NOI1997]文件匹配 深度优先搜索(DFS) 搜索KoboldsandCatacombs题解