题解 P3694 【邦邦的大合唱站队】
这个番好像很好看回头我补一补
看到数据范围容易想到是状压dp,也容易想到用dp[i],用i的二进制表示各队伍是否排好,该情况的最小所需出列人数然后就不会了.
但在这里我们需要明确一下,我们的dp[i]在这题中表示的并不是仅仅把i状态下的队伍排到一块所需的最小出队人数,而是i状态中要求完成的队伍按一定顺序,自队列最左端到右依次排好所需的最小出队人数.
如何理解这一点呢?让我们假设一组数据:
2 1 2 2 1 2 1 1
对于这组数据,我们的肉眼当然能轻易地看出只要让第二位和第六位出列,让他们互换位置即可.
但对于我们的程序而言,这里的dp[1]的值应该为3
虽然到这儿大部分同学应该没看懂,但只要知道我们的dp[i]不是仅仅把i状态下的队伍排到一块所需的最小人数就行了.
接下来我们来看一看这道题所需的变量:
int dp[1<<20];
//dp[i]表示i状态下最少所需出队人数
//此处之i状态指i的二进制下为1的队伍以从左到右的一定顺序排的状态
//例如dp[1]指将第一队所有成员排在整个队伍最左端所需最小出队人数
int sum[21][N];
//sum[j][k]表示第j队于初始队列前k个人中有多少人
int num[21];
//num[j]表示第j队总共有多少人
//以上变量都可通过初始化得到int i,j,n,m,in,l,r,SUM;
//l,r表示要把当前新加入队伍排列在l,r区间内
//SUM表示当前已排好队伍总共有多少人 随后我们就可以得出本题的状态转移方程：
意思是,我们必须要让这时候我们分配给j队的位置中不是j队的人出列
再拿之前的数据举例子:
2 1 2 2 1 2 1 1
当i=1,我们现在要让1队的人都排到最前面,但此时我们发现前4个位置中有3个人不是1队的,而dp[0]=0,故dp[1]=3.
然而我们发现,此时我们只是把前4个位置空给1队了,1队的人并没有出来,这可怎么办呢?
这并没有什么关系,因为我们发现,此后如果我们以dp[1]为基点继续dp,那些流落在外的1队队员自然也会出列,故没有问题.
那么这样每次都要求这些队伍都排在最左端,会不会漏答案呢?
并不会,因为我们最终的答案也可以看作是所有的队伍都自左边开始排列所需最小出队人数,而它一定也是可以根据上一个i状态下自左边开始排列所需最小出队人数得出的.
附完整代码以及一些注释以及一些需要注意的小点
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 100005
using namespace std;
//我也是看题解的,不过感到许多题解的一些内容不大清晰故来补一片
//所以变量雷同,纯属抄袭。
int read(){
int in=0;char c=getchar();
while(c<48 || c>57)c=getchar();
while(c>47 && c<58)in=in*10+c-48,c=getchar();
return in;
}
int dp[1<<20];
//dp[i]表示i状态下最少所需出队人数
//此处之i状态指i的二进制下为1的队伍以从左到右的一定顺序排的状态
//例如dp[1]指将第一队所有成员排在整个队伍最左端所需最小出队人数
int sum[21][N];
//sum[j][k]表示第j队于初始队列前k个人中有多少人
int num[21];
//num[j]表示第j队总共有多少人
int main(){
memset(dp,63,sizeof(dp));
dp[0]=0;
int i,j,n,m,in,l,r,SUM;
//l,r表示要把当前新加入队伍排列在l,r区间内
//SUM表示当前已拍好队伍总共有多少人
n=read();
m=read();
for(i=1; i<=n; i++){
in=read()-1;
//由于需要装压,故我们的队伍序号从0开始
num[in]++;
for(j=0; j<m; j++)
sum[j][i]=sum[j][i-1];
sum[in][i]++;
}
for(i=1; i<(1<<m); i++){
SUM=0;
for(j=0; j<m; j++)
if(i&(1<<j))
SUM+=num[j];
for(j=0; j<m; j++){
if(i&(1<<j)){
l=SUM-num[j];
r=SUM;
dp[i]=min(dp[i],dp[i^(1<<j)]+(r-l)-(sum[j][r]-sum[j][l]));
}
}
}
cout<<dp[(1<<m)-1];
return 0;
}