题目链接
题目大意
(N) 个人排成一列,每个人都有自己所属的乐队,其中第 (i) 个人一开始所在的位置为 (i)
你可以从队列中抽出任意数量的人,抽出后他们所在的位置将为空,之后你可以再把他们放进任意空位置
现要求同一个乐队的人必须站在一起,问最少要抽出多少人
解题思路
定义 (cnt[i]) 表示乐队 (i) 的总人数
定义 (dp[i]) 表示{已处理好该状态所对应的所有乐队}的最少出列个数
对于状态 (110) (二进制)
(dp[110]) 可以由 (dp[100]) 和 (dp[010]) 转移得到而 (dp[100]) 率先处理好的乐队是 (3)
可以认为率先处理好乐队 (3) 就是把该乐队成员放在 (1) ~ (cnt[3]) 的位置上
(dp[010]) 率先处理好的乐队是 (2)
可以认为率先处理好乐队 (2) 就是把该乐队成员放在 (1) ~ (cnt[2]) 的位置上
那么 (dp[110]) 就可以由{先处理 (3) 再处理 (2)} 和 {先处理 (2) 再处理 (3)} 两种情况取最优得到
同理 (dp[111]) 是由乐队 (1)、乐队 (2)、乐队 (3) 从第一个位置开始任意摆放所得到的最优解
所以我们无需再考虑摆放顺序
而将第 (i) 个乐队成员摆放在 ([L , R]) 的代价 (=) 该区间长度 (-) 该区间第 (i) 个乐队的人的个数
这步我们可以用前缀和维护
AC_Code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int dp[1 << 20];
int cnt[N] , sum[N][21];
int a[N];
int get(int l , int r , int x){
return (r - l + 1) - (sum[r][x] - sum[l - 1][x]);
}
signed main()
{
memset(dp , 0x3f3f , sizeof(dp)) , dp[0] = 0;
int n , m;
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]] ++ ;
cnt[a[i]] ++ ;
}
int up = (1 << m) - 1;
for(int i = 1 ; i <= up ; i ++)
{
int R = 0;
for(int j = 0 ; j <= m - 1 ; j ++) if(i >> j & 1) R += cnt[j + 1];
for(int j = 0 ; j <= m - 1 ; j ++) if(i >> j & 1)
{
int k = i - (1 << j);
int L = R - cnt[j + 1] + 1;
dp[i] = min(dp[i] , dp[k] + get(L , R , j + 1));
}
}
cout << dp[up] << '
';
return 0;
}