P3205

原题链接 导入 1.对于一个给定的序列，最后一个加进来的元素不是最左端就是最右端，如果是最左端，那么代表去掉最左端的序列中最后一个加进来的元素比最左端小，最右端同理。 2.对于一个给定的序列，可能的排序结果无非两类，一类是以最左端的元素结尾的，一类是以最右端的元素结尾的。因此设\(sum[i][j] ......

[Problem](https://www.luogu.com.cn/problem/P3205) ### Analysis 一道分类讨论dp 我们发现本题满足大区间包含小区间，区间之间可以互相推导，符合区间dp。 再看看我们需要记录什么？我们发现哪一个数最后放会影响到决策，所以我们需要记录这一层状 ......

P3205 [HNOI2010]合唱队 区间DP——取一端 思: 根据题意我们发现，每次排队的时候，会出现两种情况 当前排入的人(即初始队列最后一人)比初始队列中前一个人矮，排到最左边 当前排入的人(同上)比初始队列中前一个人高，排到最右边 可从初始队列最后一人切入。 设置状态:$f[l][r][0 ......