CF1886E 题解

CF1886E

思路

观察发现每个项目只与程序员数量和最小值有关，所以每个项目对应能力值连续的程序员最优。

项目数 \(m\le 20\)，状压。设 \(dp_{i,s}\) 为前 \(i\) 个程序员匹配的项目状态为 \(s\) 是否可行，无法接受。交换维度，改为 \(dp_s\) 表示状态 \(s\) 能与前缀 \([1,i]\) 匹配的最小 \(i\)。

不要求全选程序员，全选不一定优。预处理 \(f_{i,s}\) 表示第 \(i\) 个项目从 \(j\) 开始匹配程序员，最少要匹配到哪里。\(f_{i,j}=\min(f_{i,j+1},j+\lceil\frac{b_i}{a_j}\rceil-1)\)。

code

int n,m;
pii a[maxn];int b[maxn];
int dp[1<<20],pre[1<<20],f[20][maxn];
pii pos[20];
void work(){
	n=read();m=read();
	for(int i=1;i<=n;i++)a[i]={read(),i};
	for(int i=0;i<m;i++)b[i]=read();
	sort(a+1,a+n+1);
	for(int i=0;i<m;i++){
		f[i][n+1]=n+1;
		for(int j=n;j;j--)f[i][j]=min(f[i][j+1],j+(b[i]+a[j].fi-1)/a[j].fi-1);
	}
	mems(dp,0x3f);dp[0]=0;
	for(int s=1;s<(1<<m);s++){
		for(int i=0;i<m;i++)if(s&(1<<i)){
			if(dp[s^(1<<i)]>=n)continue;
			if(f[i][dp[s^(1<<i)]+1]<dp[s])dp[s]=f[i][dp[s^(1<<i)]+1],pre[s]=i;
		}
	}
	if(dp[(1<<m)-1]>n){printf("NO\n");return ;}
	printf("YES\n");
	int s=(1<<m)-1;
	while(s){
		for(int i=dp[s^(1<<(pre[s]))]+1;i<=dp[s];i++)if(f[pre[s]][i]!=f[pre[s]][i+1]){
			pos[pre[s]]={i,dp[s]};
			break;
		}
		s^=(1<<pre[s]);
	}
	for(int i=0;i<m;i++){
		printf("%lld ",pos[i].se-pos[i].fi+1);
		for(int j=pos[i].fi;j<=pos[i].se;j++)printf("%lld ",a[j].se);printf("\n");
	}
}