CF1316E Team Building 题解

· · 题解

可能更好的阅读体验

题目传送门

题目大意

传送门
你需要组建一支排球队。为了组织一支排球队，你需要为队伍里的 p 个不同的位置，从 n 个人中选出 p 个人，且每个位置上都恰好有一个人。另外还需要从剩下的人中选出恰好 k 个人作为观众。
对于第 i 个人，已知他作为观众时能为队伍增加 a_i 点力量，还有他在队伍的第 j 个位置上时能为队伍增加 s_{i,j} 点力量。请问这只排球队力量的最大值是多少？

n,k\le 10^5$，$p\le 7$，$a_i,s_{i,j}\le 10^9

题目解析

CF 2300，好像也不是很难，评紫题过分了昂 显然把上场的队员选定之后，那么剩下的肯定是选择贡献大的当做观众。
那么就把所以人作为观众的贡献降序排序，考虑在这个序列上 DP。

问题在于怎么转移。设 $f_{i,j}$ 为前面 $i$ 个中选择情况状态压缩之后为 $j$ 的贡献最大值，不妨设 $j$ 二进制位 $1$ 的个数（也就是选择作为运动员的个数）是 $now$。 考虑从之前的转移。分两种情况讨论。 如果 $i>p+now$，那么这个人不是观众，所以直接加上作为运动员的贡献即可。 如果 $i\le p+now$，那么这个人是观众，所以还要减去这个人当前作为观众贡献，然后第 $p+now$ 个人就成为了观众，需要加上此人的贡献。 时间复杂度 $\Theta(np2^p) 
int n,p,m,msk;
struct JTZ{
    int au,pl[maxm];
    bool operator < (const JTZ x) const {
        return this->au > x.au;
    }
}a[maxn];
ll f[2][139];
int main(){
    n=read(); p=read(); m=read(); msk=(1<<p)-1; int i,j,k,now; for(i=1;i<=n;i++) a[i].au=read();
    for(i=1;i<=n;i++) for(j=0;j<p;j++) a[i].pl[j]=read();
    sort(a+1,a+n+1); for(i=1;i<=m;i++) f[0][0]+=a[i].au;
    for(i=1;i<=n;i++) for(j=0;j<=msk;j++){
        now=0; f[i&1][j]=f[(i&1)^1][j]; for(k=0;k<p;k++) if(j&(1<<k)) now++;
        for(k=0;k<p;k++) if(j&(1<<k)){
            if(i>m+now) f[i&1][j]=mmax(f[i&1][j],f[(i&1)^1][j^(1<<k)]+a[i].pl[k]);
            else f[i&1][j]=mmax(f[i&1][j],f[(i&1)^1][j^(1<<k)]+a[i].pl[k]-a[i].au+a[m+now].au);
        }
    } print(f[n&1][msk]); return 0;
}