洛谷P3694

题意：

有$n$个人，他们属于$m(m\le 20)$个团队之一，每个人属于的团队是$a_i$，现在给出从前到后他们排队的顺序。可以将任意个人移出队列，然后将每个人移入任意位置，问至少要移出多少个人，才能使得队列中同一团队的人都连续的站在一起？

方法：

由于$m\le 20$，所以想到状态压缩$dp$，接下来是如何设置状态

要状压，首先肯定有一维是团队的状态，设$dp[s]$是团队的归队集合为$s$，达成这样的最少出列人数是$dp[s]$。

先考虑一下转移方程，转移方程很简单

$$dp[s|(1<<(i-1))]=min(dp[s|(1<<(i-1))],dp[s]+cost)$$

其中$cost$是接下来放置所有$i$团队的出列个数，显然，根据状态$s$有多少个$1$，我们可以知道放置好了多少个人$tot$，接下来就会在

$[tot+1,tot+su{m}_i]$放置$i$团队，可以双指针预处理出来每个位置为开头放置团队$i$的代价，这样转移就是$O(1)$的

这样包含了所有状态吗？归队的集合为$s$，那么归队的顺序如何呢？

由于$dp[s]$会被所有$dp[s-(1<<(i-1))]$更新，也就是每个$dp[s]$已经在所有顺序里面取得最小值了，所以顺序这一状态已经包含，那么这样就已经包含了所有状态了

#include
using ll=long long;
using namespace std;

int cost[21][100005],tot[21];
int n,m,val[100005],dp[(1<<21)+5];

int gettot(int s)
{
    int ret=0;
    for(int i=1;i<=m;i++)
        if(s>>(i-1)&1) ret+=tot[i];
    return ret;
}
/*
12 4 
1 3 2 4 2 1 2 3 1 1 3 4
*/
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&val[i]);
        tot[val[i]]++;
    }
    //cost[i][j] 第i个集团从j位置开始放，有几个是不在位置上的？
    for(int i=1;i<=m;i++)
    {
        auto add=[&](int x){return val[x]!=i;};//第x个位置是不是i
        int ans=add(1),l=1,r=1;
        while(r<tot[i]) ans+=add(++r);
        while(r<=n)
        {
            cost[i][l]=ans;
            ans+=add(++r)-add(l++);
        }
    }
    for(int s=1;s<(1<<m);s++) dp[s]=0x3fffffff;
    for(int s=0;s<(1<<m)-1;s++)
    {
        for(int i=1;i<=m;i++)
        {
            if(s>>(i-1)&1) continue;
            dp[s|(1<<(i-1))]=min(dp[s|(1<<(i-1))],dp[s]+cost[i][gettot(s)+1]);
        }
    }
    cout<<dp[(1<<m)-1];
    return 0;
}