这一道题目看到\(m\)很小，考虑状压
这个状压的状态只考虑了前\(l[S]\)的位置，后面的人都忽略了。由数学归纳法可以知道，这其实是正确的
我还要证明一下这种转移的正确性：即证明对一个区间\([1,r]\)，当乐队顺序固定后，出列的人数最少就是\(r-\)一开始就在对应乐队的区间中的人数
其实用微扰很容易证明，如果存在一种最优方案，让某一个本来最开始就匹配的人（设为\(i\)）出列了，那么最后这个人一定会走到这个乐队区间的另一个位置（设为\(j\)），然后他的这个原来的位置（\(i\)）就会被另一个人（设为\(k\)）来填充，如果是这样的话我们不如直接让\(i\)不出列，然后让\(k\)去填充\(j\)
我最开始的时候认为状态要把整个区间（即\([1,N]\)）都考虑进去，所以我的\(f[i]\)表示状态为\(i\)的时候，不在\(i\)里面的乐队可以随便排的最少出队人数
倒是也能做，但是很麻烦，此时人数还是按照上面这样算，然后枚举最后一个乐队是多少，但是不能用\(i\)去除这最后一支的状态的\(f\)来转移，而是应该预处理另一个数组来转移。我们将出队人数分为三部分：第一部分就是最后一支队伍的不匹配人数，与\(i\)剩下的乐队怎么排列无关；第二部分就是\(i\)之外的乐队（排在\(l[S]\)后面），也与\(i\)剩下的乐队怎么排列无关；第一部分就是\(i\)剩下的乐队排列后的不匹配人数。以上三部分中的后两个部分需要预处理两个数组来进行转移
当然这道题目启发我们，费用提前计算别做多了。。只考虑当前状态是一个很典型的DP思想呀
标签：状态,大合唱,部分,乐队,站队,区间,出列,人数 From： https://www.cnblogs.com/dingxingdi/p/17996770