C 战棋小孩

原题链接

先亮个出题人的题解：

出题人讲的还比较简洁清晰，但我认为证明的最后那里有个小跳步，可能出题人觉得比较显然就没有展开讲吧。首先做一次逆序交换答案会变劣是显然的，然后我们可以得知一个倒序排列的序列可以经过若干次逆序对交换变成这个序列经过全排列后的任何一种情况。那么也就是说任何一种其它的排列都是经过这个倒序的排列经过若干次劣化得来的，所以答案只可能会变劣，因此倒序排列是最优的。

CODE:

#include <bits/stdc++.h>

using namespace std;

const int N = 30;

int n, k, s, p[N];

int a[30][5], w[30], mx[30][3];

bool cmp(int a, int b) {return a > b;}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    cin >> n >> k >> s;
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
    }
    for (int i = 1; i <= n; ++i) {
        mx[i][1] = mx[i][2] = -1e9;
        for (int j = 1; j <= 4; ++j) {
            cin >> a[i][j];
            if (j <= 2) mx[i][1] = max(mx[i][1], a[i][j]);
            mx[i][2] = max(mx[i][2], a[i][j]);
        }
    }
    
    int ans = 0;
    for (int i = 0; i < (1 << n); ++i) {
        int alll = 0;
        for (int j = 0; j < n; ++j) {
            w[j + 1] = mx[j + 1][1];
            if (((i >> j) & 1)) {
                w[j + 1] = mx[j + 1][2];
                alll++;
            }
        }
        if (alll > k) continue;
        sort(w + 1, w + 1 + n, cmp);
        int cnt = 0;
        w[0] = s;
        for (int j = 1; j <= n; ++j) {
            w[j] += w[j - 1];
            if (w[j] >= p[j]) cnt++;
        }
        ans = max(ans, cnt);
    }
    cout << ans << endl;
}