题目背景
BanG Dream!里的所有偶像乐队要一起大合唱，不过在排队上出了一些问题。
题目描述
N个偶像排成一列，他们来自M个不同的乐队。每个团队至少有一个偶像。
现在要求重新安排队列，使来自同一乐队的偶像连续的站在一起。重新安排的办法是，让若干偶像出列（剩下的偶像不动），然后让出列的偶像一个个归队到原来的空位，归队的位置任意。
请问最少让多少偶像出列？
输入输出格式
输入格式：
第一行2个整数N，M。
接下来N个行，每行一个整数 a_i(1\le a_i \le M)ai(1≤ai≤M) ，表示队列中第i个偶像的团队编号。
输出格式：
一个整数，表示答案
输入输出样例
12 4
1
3
2
4
2
1
2
3
1
1
3
4
7
说明
【样例解释】
1 3 √
3 3
2 3 √
4 4
2 4 √
1 2 √
2 2
3 2 √
1 1
1 1
3 1 √
4 1 √【数据规模】
对于20%的数据， N\le 20, M=2N≤20,M=2
对于40%的数据， N\le 100, M\le 4N≤100,M≤4
对于70%的数据， N\le 2000, M\le 10N≤2000,M≤10
对于全部数据， 1\le N\le 10^5, M\le 201≤N≤105,M≤20
Solution
本蒟蒻做的第一道状压DP. 发现根本不会怎么搞...结果竟然不仅看了题解定义的状态,居然还看了转移方程(我也是水到了一定境界).
看来 DP 还是不够啊 ! ! 进入正题:
首先关于题意,有几点需要注意:
1.每个人离开之后,会有一个空位,而且肯定会有另外一个人补上来.
2.最终状态不一定要求团队按正序排列.
状态定义:
f [ i ] 表示当前达到这种状态所需要请出去的最少的人.
然后关于 i 转为 二进制后上的每一位,都表示当前这个团队已经站在了一起.
然后转移方程:
f[i]=min(f[i xor 2j]+num[j]−(sum[length][j]−sum[length−num[j]][j]));
j表示团队编号,sum表示某种团队的前缀和.length表示到此已经排到的长度.
然后代码里面有解释.
#include<bits/stdc++.h>
using namespace std;
int n,m;
int c[],f[];
int sum[][];
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
scanf("%d",&c[i]);
c[i]--;
//减掉一维可以省空间
for(int j=;j<m;j++)
{
sum[i][j]=sum[i-][j];
if(j==c[i])
sum[i][j]++;
}
}
for(int i=;i<(<<m);i++)
f[i]=;
//赋值为极大值
f[]=;
for(int i=;i<(<<m);i++)
{
int now=;
//now表示当前这个状态哪一些单位无需处理.
for(int j=;j<m;j++)
if((<<j)&i) now+=sum[n][j];
for(int j=;j<m;j++)
{
if((<<j)&i) continue;
int num=sum[n][j];
int r=now+num;
int l=now;
f[i|(<<j)]=min(f[i|(<<j)],f[i]+(r-l-(sum[r][j]-sum[l][j])));
/*此时的决策:
即新加一个团队. 更新状态:
需要先计算当前这种情况所达到的点.
即满足当前这种情况的话,我们已经到了何处.
然后的话,我们此时需要将后面的这个团队的人补上来.
所以需要花费的代价即是
当前这个团队所有的人
减去当前这个点所有的这个团队的人 */
}
}
printf("%d\n",f[(<<m)-]);
return ;
}