Codeforces

Luogu

分析

有一个显然的状压 DP：设 $dp_{i,S}$ 表示前 $i$ 个人，$S$ 中的位置被选中时的最大力量值，转移枚举当前这个人当观众还是进某个位置即可。

然而 $p+k\leq n$，所以这个做法不太行。

注意到我们一定会选择 $a_i$ 较大的那些人当观众。将所有人按 $a_i$ 从大到小排序，当 $i-|S|>k$ 时 $i$ 显然不会被选为观众，改一下转移即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define popcount(S) __builtin_popcount(S)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,p,k;
struct node { int a,s[8]; } a[N];
ll dp[N][1<<7];

int main() {
    n=read(),p=read(),k=read();
    for (int i=1;i<=n;++i) a[i].a=read();
    for (int i=1;i<=n;++i)
        for (int j=1;j<=p;++j) a[i].s[j]=read();
    sort(a+1,a+n+1,[](node i,node j) { return i.a>j.a; });
    memset(dp,0xc0,sizeof(dp)); dp[0][0]=0;
    for (int i=1;i<=n;++i)
        for (int S=0;S<1<<p;++S) {
            if (i-popcount(S)<=k) dp[i][S]=dp[i-1][S]+a[i].a;
            else dp[i][S]=dp[i-1][S];
            for (int j=1;j<=p;++j)
                if (S&(1<<(j-1)))
                    dp[i][S]=max(dp[i][S],dp[i-1][S^(1<<(j-1))]+a[i].s[j]); 
        }
    printf("%lld\n",dp[n][(1<<p)-1]);
    return 0;
}