邦邦的大合唱站队

标签： 动态规划 状态压缩

---

题目描述

$N(1<=N<=10^5)$个偶像排成一列，他们来自$M(1<=M<=20)$个不同的乐队。每个团队至少有一个偶像。

现在要求重新安排队列，使来自同一乐队的偶像连续的站在一起。重新安排的办法是，让若干偶像出列（剩下的偶像不动），然后让出列的偶像一个个归队到原来的空位，归队的位置任意。

请问最少让多少偶像出列？

输入输出格式

输入格式：

第一行2个整数N，M。
接下来N个行，每行一个整数$ai$($1≤ai≤M)$，表示队列中第i个偶像的团队编号。

输出格式：

一个整数，表示答案

输入输出样例

输入样例#1：
12 4
1
3
2
4
2
1
2
3
1
1
3
4

输出样例#1：
7

题解

看到M这么小，容易联想到状态压缩。有一个性质是，对于两个偶像编号相同的人来说，他们是等价的。（emmmm…就是这两人没区别）
因此我们逆向思考：设计一种偶像团队编号的排列方式，使得尽可能多的人站在属于自己偶像编号位置上。（就是使得尽可能多的人不用出列换位置）
我们设f[i]表示偶像编号排列状态为i时，最大的不用换位置的偶像数。
转移方程:

ass_max(f[i | (1 << (j - 1))], f[i] + sum[g[i] + cnt[j]][j] - sum[g[i]][j]);

其中g[i]表示状态为i时的总人数。cnt[j]表示偶像编号为j的总人数
sum[i][j]表示前i个人编号为j的人数。

代码

#include<bits/stdc++.h>
#define N 100010
#define M 20
using namespace std;

int n, m;
int a[N], cnt[M], sum[N][M], g[1 << M], f[1 << M];
void ass_max(int &a, int b) {a = a > b ? a : b;}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &a[i]);
        sum[i][a[i]] ++;
        cnt[a[i]] ++;
    }
    for(int i = 1; i <= m; i ++)
        for(int j = 1; j <= n; j ++)
            sum[j][i] += sum[j - 1][i];
    memset(f, -1, sizeof(f));
    f[0] = 0;
    for(int i = 0; i < (1 << m); i ++)
        for(int j = 1; (1 << (j - 1)) <= i; j ++)
            if(i & (1 << (j - 1)))
               g[i] += cnt[j];
    for(int i = 0; i < (1 << m); i ++)
        for(int j = 1; j <= m; j ++)
            if(!(i & (1 << (j - 1))) && f[i] != -1)
               ass_max(f[i | (1 << (j - 1))], f[i] + sum[g[i] + cnt[j]][j] - sum[g[i]][j]);
    printf("%d", n - f[(1 << m) - 1]);
    return 0;
} 

心得

有时候逆向思考问题可以得到很不错的结果啊。