CF1316E Team Building

CF1316E 【Team Building】

状压dp，感觉比D简单

\(f[i][s]\)，表示考虑前\(i\)个人，状态为\(s\)（\(s\)的第\(j-1\)个二进制位表示队员的第\(j\)个位置有没有人）的最大价值

考虑如何转移

 

如果不让第\(i\)个人当队员

• 如果当前已选为观众的人不足\(k\)个，则一定让它当观众，那么\(f[i][s]\)由\(f[i-1][s]+a_i\)转移来，不过这样做的前提是要先把这\(i\)个人按照他们当观众时的价值排序，从而如果当前观众不到\(k\)个但不选第\(i\)个，就一定会在后面选一个\(j(j>i)\)当观众，\(a_j<a_i\)，就没有选第\(i\)个优了
• 如果已经选了\(k\)个，不能再选直接\(f[i][s]=f[i-1][s]\)

已经选了几个要通过\(s\)确定，也就是\(i-1-s\text{在二进制中1的个数}\) 个人已被选位观众

 

让第\(i\)个人当队员

枚举把\(i\)放在哪一位，如果要将他放在第\(j\)位，则需满足\(s\)的第\(j-1\)个二进制位为1（也就是当前的状态这一个位置有人）,那么\(f[i][s]\)可以由\(f[i-1][s \oplus (j-1)]+s_{i,j}\)转移而来

这里异或的意义就是把\(s\)的第\(j-1\)个二进制位从1变0，被转移的状态肯定是第\(j\)个位置没人

那么就可以写出代码了，其实整个思考的最重要部分就在于把\(n\)个人排序，来实现 能被选去当观众就一定选，就能达到最优 的效果，复杂度\(O(np2^p)\)

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cmath>

#include<iomanip>

#include<cstring>

#define reg register

#define EN std::puts("")

#define LL long long

inline int read(){

	int x=0,y=1;

	char c=std::getchar();

	while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}

	while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}

	return y?x:-x;

}

int n,p,k;

struct data{

	int v,id;

	LL s[10];

}a[100006];

LL f[100006][130];

inline int cmp(data aa,data aaa){return aa.v>aaa.v;}

int main(){

	n=read();p=read();k=read();

	for(reg int i=1;i<=n;i++) a[i].v=read(),a[i].id=i;;

	for(reg int i=1;i<=n;i++)

		for(reg int j=1;j<=p;j++) a[i].s[j]=read();

	reg int lim=1<<p;

	std::sort(a+1,a+1+n,cmp);

	std::memset(f,-1,sizeof f);

	f[0][0]=0;

	for(reg int i=1;i<=n;i++){

		for(reg int s=0;s<lim;s++){

			int cnt=0;

			for(reg int j=0;j<p;j++)

				if(s&(1<<j)) cnt++;

			int tmp=i-1-cnt;

			if(tmp<k){

				if(f[i-1][s]!=-1) f[i][s]=f[i-1][s]+a[i].v;;

			}

			else f[i][s]=f[i-1][s];

			for(reg int j=1;j<=p;j++){

				if((s&(1<<(j-1)))&&f[i-1][s^(1<<(j-1))]!=-1)

					f[i][s]=std::max(f[i][s],f[i-1][s^(1<<(j-1))]+a[i].s[j]);

			}

		}

	}

	std::printf("%lld",f[n][lim-1]);

	return 0;

}