题目传送门

题目大意：

个人，从中选择个作为球员，第个人产生，个作为观众，第个人产生的价值

解题思路

不难想，通过对用二进制进行状态压缩，到一个简单的过程
这种做法的复杂度大约是显然是不可接受的
然后不难发现作为观众的人，其实只要贪心的在没有选为球员的人里面选最大的个就好了
于是又得以去掉的复杂度，于是就可以接受了
设为前个人中选择状态为的最大价值，所有人先按降序排序
如果时，直接将加入答案，其中表示在二进制表示下的个数。
因为此时剩余可选人数不足人，显然所有剩余的都是最优的。否则在这种状态下肯定已经选择了个最优的，不用再选择了
之后枚举,将第个人放在第个位置,当时因为状态从转移过来，不用担心前一步选择的影响，保证了无后效性

AC代码

//#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <list>
#include <cstdlib>
#include <bitset>
#include <assert.h>
#include <iomanip>
// #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
// char buf[(1 << 21) + 1], * p1 = buf, * p2 = buf;
// #define int long long
#define lowbit(x) (x & (-x))
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
#define pb push_back
typedef unsigned long long ull;
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, ll> pll;
#define bug puts("BUG")
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
const int mod = 97654321;
const double eps = 1e-6;
template <class T>
inline void read(T &x)
{
    int sign = 1;char c = getchar();x = 0;
    while (c > '9' || c < '0'){if (c == '-')sign = -1;c = getchar();}
    while (c >= '0' && c <= '9'){x = x * 10 + c - '0';c = getchar();}
    x *= sign;
}
#ifdef LOCAL
    FILE* _INPUT=freopen("input.txt", "r", stdin);
    // FILE* _OUTPUT=freopen("output.txt", "w", stdout);
#endif
using namespace std;
const int maxn = 1e5 + 10;
int s[maxn][7], sz[1 << 7];
int a[maxn], pos[maxn];
bool cmp(int i, int j)
{
    return a[i] > a[j];
}
ll dp[2][1 << 7];
int main()
{
    int n, p, k;
    read(n), read(p), read(k);
    for (int i = 1; i <= n; ++i)
    {
        read(a[i]);
        pos[i] = i;
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < p; ++j)
        {
            read(s[i][j]);
        }
    }
    for (int i = 0; i < (1 << p); ++i)
    {
        sz[i] = sz[i >> 1] + (i & 1);
    }
    sort(pos + 1, pos + 1 + n, cmp);
    int now = 0, pre = 1;
    memset(dp, 0x80, sizeof dp);//0x80808080 < 0
    dp[now][0] = 0;
    for (int v = 1; v <= n; ++v)
    {
        int i = pos[v];
        swap(now, pre);
        memset(dp[now], 0x80, sizeof dp[now]);
        for (int j = 0; j < (1 << p); ++j)
        {
            if (dp[pre][j] < 0)
                continue;
            if (v - sz[j] <= k)
                dp[now][j] = max(dp[now][j], dp[pre][j] + a[i]);
            else
                dp[now][j] = max(dp[now][j], dp[pre][j]);
            for (int l = 0; l < p; ++l)
                if ((j | (1 << l)) != j)
                {
                    dp[now][j | (1 << l)] = max(dp[now][j | (1 << l)], dp[pre][j] + s[i][l]);
                }
        }
    }
    printf("%lld\n", dp[now][(1 << p) - 1]);
}