P3694 邦邦的大合唱站队 题解

原题链接：P3694

思路

• 状态设计

因为这道题 \(m\) 的范围非常小，所以可以用 \(m\) 来作为状态。设 \(dp_{i}\) 表示
\(m\) 支队伍的状态为 \(i\) 时最少让多少偶像出列。

• 预处理

在转移之前，我们先要预处理出序列的前缀和 \(sum_{i,j}\) 表示第 \(i\) 个数之前有多少个值为 \(j\) 的数，方法如下：

for(int i = 1;i <= n;i++) 
	{
		cin >> a[i];
		for(int j = 1;j <= m;j++) sum[i][j] = sum[i - 1][j];
		sum[i][a[i]]++;
	}

还需要预处理出 \(s_{i}\) 表示 \(i\) 状态中一共有多少个人。只需要将状态 \(i\) 中的每一个数抽出来分解一下即可。

for(int i = 0;i < (1 << m);i++)
	{
		int now = i,cnt = 0;
		while(now != 0)
		{
			++cnt;
			if(now & 1) s[i] += sum[n][cnt];
			now >>= 1;
		}
	}

• 方程转移

首先我们假设当前队伍是 \(j\)，现在的状态是 \(i\)，那么新加的需要出列的人就是 \(sum_{n,j}-sum_{s_{i},j}+sum_{s_{i xor (1<<j-1)}}\)，相当于是用了前缀和的思想。所以 \(dp\) 方程转移为：

int l = s[i ^ (1 << j - 1)],r = s[i];
dp[i] = min(dp[i],dp[i ^ (1 << j - 1)] + sum[n][j] - sum[r][j] + sum[l][j]);

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls id << 1
#define rs id << 1 | 1
#define inf 0x3f
#define inf_db 127
typedef pair <int,int> pii;
const int MAXN = 1e5 + 10;
const int MAXM = (1 << 20) + 10;
const int M = 30;
int n,m,a[MAXN],dp[MAXM],sum[MAXN][M],s[MAXM];
signed main()
{
	cin >> n >> m;
	for(int i = 1;i <= n;i++) 
	{
		cin >> a[i];
		for(int j = 1;j <= m;j++) sum[i][j] = sum[i - 1][j];
		sum[i][a[i]]++;
	}
	for(int i = 0;i < (1 << m);i++)
	{
		int now = i,cnt = 0;
		while(now != 0)
		{
			++cnt;
			if(now & 1) s[i] += sum[n][cnt];
			now >>= 1;
		}
	}
	memset(dp,inf,sizeof dp);
	dp[0] = 0;
	for(int i = 0;i < (1 << m);i++)
		for(int j = 1;j <= m;j++)
		{
			if(!(i & (1 << j - 1))) continue;
			int l = s[i ^ (1 << j - 1)],r = s[i];
			dp[i] = min(dp[i],dp[i ^ (1 << j - 1)] + sum[n][j] - sum[r][j] + sum[l][j]);
		}
	cout << dp[(1 << m) - 1];
	return 0;
}