[ABC424G] Set list 题解

乍一看感觉很难直接 DP，于是考虑先把限制形式化。设当前选的歌曲形成的集合是 ，因为歌曲的顺序并不影响所选集合的合法性，所以 。考虑简化条件，对于一个固定的 ，要最大化前者，显然只需要取较大的几个 。所以自然想到先将 （连带着 ）降序排序，条件就转化为了 ，记后者为 ，它是可以预处理出来的。可以证明这个条件是充要的，一个感性的理解是，我们取出了原集合的每一个子集并判断其是否合法，具体的证明可以参见 Atcoder 的 官方题解。

那么接下来就好做了。设 表示前 首歌中选了 首歌，且 的最大价值。转移类似于背包，把 视为当前背包容量，把 视为已用的容量，把 与 视为当前物品的体积与价值。时间复杂度 ，空间复杂度 。

#include <bits/stdc++.h>

#define rep(i, s, e) for(int i = s; i <= e; ++i)
#define _rep(i, s, e) for(int i = s; i >= e; --i)

using namespace std;

int n, m, a[105], mx[105];
pair<int, int> b[105];
long long dp[105][10005], ans;

signed main() {
	scanf("%d %d", &n, &m);
	rep(i, 1, n) {
		scanf("%d", &a[i]);
	}
	rep(i, 1, m) {
		scanf("%d %d", &b[i].first, &b[i].second);
	}
	sort(b + 1, b + 1 + m, greater<pair<int, int>>());
	rep(i, 1, m) {
		rep(j, 1, n) {
			mx[i] += min(a[j], i);
		}
	}
	rep(j, 0, m) {
		rep(k, 0, n * m) {
			dp[j][k] = - (1ll << 60);
		}
	}
	dp[0][0] = 0;
	rep(i, 1, m) {
		_rep(j, i, 1) {
			_rep(k, mx[j], b[i].first) {
				dp[j][k] = max(dp[j][k], dp[j - 1][k - b[i].first] + b[i].second);
			}
		}
	}
	ans = 0;
	rep(j, 0, m) {
		rep(k, 0, n * m) {
			ans = max(ans, dp[j][k]);
		}
	}
	printf("%lld\n", ans);
	return 0;
}