题解 | #疫苗小孩#

观察到序列长度<=20,那么显然我们可以用状态压缩去枚举我们的礼遇用在那一场战斗, 1<<20=1024*1024复杂度可以接受。

即我们用一段01串去模拟使用礼遇和不使用的场景。

当第j位上为1的时候则我们可以在4个数中取max，即使用礼遇，否则只能在两个数中取最大值。

当然，我们的01串中1的数量不可以大于k

这样我们就能得到我们的得分序列，然后在贪心的从大到小排序去看我们能否符合最小得分即可

举个状态压缩的例子当我们的比赛场次为3的时候，我们的01串可以是000, 001, 010,....,111。

那么他们的十进制分别是0，1，2，...,7。而(1<<3)-1恰好就是7。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 2e6 + 10;
const int mod = 1e9 + 7;

int n, k, s;
int ans;
struct node
{
	int a, b, c, d;
}g[30];

int main()
{
	cin >> n >> k >> s;
	vector<int> a(n);

	for(int i = 0; i < n; i ++) {
		cin >> a[i];
	}
	for(int i = 0; i < n; i ++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		g[i] = {a, b, c, d};
	}

	for(int i = 0; i < (1 << n); i ++) {
		vector<int> t;
		for(int j = 0; j < n; j ++) {
			if(i >> j & 1) {
				t.emplace_back(j);
			}
		}

		if(t.size() > k) {
			continue;
		}

		vector<int> res;
		int l = 0;
		for(int j = 0; j < n; j ++) {
			if(l < t.size() && t[l] == j) {
				res.emplace_back(max({g[j].a, g[j].b, g[j].c, g[j].d}));
				l ++;
			} else {
				res.emplace_back(max(g[j].a, g[j].b));
			}
		}

		sort(res.begin(), res.end(), greater<int>());
		int cnt = 0, all = s;

		for(int j = 0; j < res.size(); j ++) {
			all += res[j];
			if(all >= a[j]) {
				cnt ++;
			}
		}
		ans = max(ans, cnt);
	}

	cout << ans;
	
	return 0;
}

百色疫情加油QAQQ