洛谷

洛谷题单指南-状态压缩动态规划-P3694 邦邦的大合唱站队

原题链接：https://www.luogu.com.cn/problem/P3694

题意解读：N个人属于M个组，给出N个人的排列，要将同组人排在一起，问至少多少人出列后再重排可以实现。

解题思路：

1、暴力思路

对M个组进行全排列，由于每个组有多少人已知，这样每个组所在区间可以明确；

然后可以枚举每个人，看每个人的组与该位置所在区间的组是否对应，不对应则出列，统计出列总人数；

所有排列的出列总人数取最小值。以上时间复杂度为O(N*M!)。

可以进一步优化，通过s[i][j]预处理第i组在前j个人一共有多少个，通过区间和即可计算任意区间任意组的总人数，根据组的排列的所有位置组的总人数减去该区间实际对应组的人数即使该区间要出列的人数。优化后时间复杂度为O(M*M!)。

70分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005, M = 25, INF = 0x3f3f3f3f;
int a[M];
int cnt[M]; //cnt[i]表示第i组的人数
int s[M][N]; //s[i][j]表示第i组在前j个人里一共有多少个
int n, m, ans = INF;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        cnt[x]++;
        s[x][i]++;
    }
    //求每个组的前缀和
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            s[i][j] += s[i][j - 1];

    //全排列
    for(int i = 1; i <= m; i++) a[i] = i;
    do
    {
        int sum = 0, res = 0;
        for(int i = 1; i <= m; i++) //枚举每个组
        {
            int g = a[i];
            int l = sum + 1; //当前组区间左端点
            sum += cnt[g];
            int r = sum; //当前组区间右端点
            res += cnt[g] - (s[g][r] - s[g][l - 1]);
        }
        ans = min(ans, res);
    } while (next_permutation(a + 1, a + m + 1));

    cout << ans;
    return 0;
}

2、动态规划

M!的复杂度是不可接受的，要优化到2^M，可以借助于状态压缩。

设f[i]表示队列最前面状态为i的组都已经排好的最少出队人数，比如i = 1001表示队列最前面第1、4组的人都已经排好；

状态如何转移？

对于任意状态，可以枚举接下来排好的是哪个组，也就是在i的二进制0~m-1位置找值是0的位置j，对应组j+1，组的总人数是cnt[j+1]，已经排好组的总人数

也可以计算得到，设为sum，通过区间sum + 1 ~ sum + cnt[j+1]可以求得j+1组要出列的人数。

对所有接下来排好的组的最少出列人数求min，转移方程为：

f[i | 1 << j] = min(f[i | 1 << j], f[i] + cnt[j+1] - (s[j+1][sum+cnt[j+1]] - s[j+1][sum]))

初始化：f[0] = 0，其余为INF

结果：f[(1 << m) - 1]

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005, M = 25, INF = 0x3f3f3f3f;
int cnt[M]; //cnt[i]表示第i组的人数
int s[M][N]; //s[i][j]表示第i组在前j个人里一共有多少个
int f[1 << 20]; //f[i]表示队列最前面状态为i的组都已经排好的最少出队人数
int n, m;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        cnt[x]++;
        s[x][i]++;
    }
    //求每个组的前缀和
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            s[i][j] += s[i][j - 1];

    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    for(int i = 0; i < (1 << m) - 1; i++)
    {
        int sum = 0;
        for(int j = 0; j < m; j++)
            if(i >> j & 1)
                sum += cnt[j + 1]; //前面已排好的组的人数
        for(int j = 0; j < m; j++)
            if(!(i >> j & 1)) //枚举下一个排好的组
                f[i | 1 << j] = min(f[i | 1 << j], f[i] + cnt[j + 1] - (s[j + 1][sum + cnt[j + 1]] - s[j + 1][sum]));   
    }

    cout << f[(1 << m) - 1];
    return 0;
}