题

小L养了很多马，朋友说在景区收费骑马可以赚很多钱，于是小L想试一试。小L在某4A景区内，收费骑马，有三个项目，骑大圈，骑小圈，过河。小L在正式开业前，有一天试营业，他提前在网上约了朋友，朋友们已经告诉小L他们想要体验的项目。小L想尽可能多地满足朋友们的需求，但他也不希望有马太过劳累而导致生病。小L定义疲劳值，当一匹马的疲劳值大于 100 时（初始时疲劳值为 1），马会累倒，小L会生气。

小L拜托你求出最多可以满足几位朋友的要求，他一共有 $n$ 匹马，有 $m$ 个朋友答应来，骑小圈马的疲劳值加 20；骑大圈，疲劳值加 50；过河，疲劳值乘 2。

$n\leq150,m\leq300$ 。

解

考虑一个马要过河肯定会在做所有操作之前过河，我们用三元组 $(i,j,k)$ 表示一个马过 $i$ 次河，跑 $j$ 次大圈，后最多可以跑 $k$ 次小圈，则只有 $(0,1,2),(0,0,4),(1,1,2),(1,0,4),(2,1,2),(2,0,4),(3,1,2),(3,0,4),(4,1,1),(4,0,4),(5,1,0),(5,0,3),(6,0,1)$ 这些三元组。

如果有 $x\leq i,y\leq j,z\leq k$ ，那么一匹马选 $(x,y,z)$ 一定没有选 $(i,j,k)$ 优秀，我们可以不考虑 $(x,y,z)$ ，我们去除所有这些三元组之后给余下的三元组按是否跑了大圈分类，两类分别为 $\{(4,0,4),(5,0,3),(6,0,1)\}$ 和 $\{(3,1,2),(4,1,1),(5,1,0)\}$ 。

我们发现，两匹马选择了 $(4,1,1)$ 等价于它们分别选择 $(3,1,2)$ 和 $(5,1,0)$ ，因此一定存在一组最优方案，其中至多只有一匹马选择了 $(4,1,1)$ 。我们 $\mathcal{O}(n^2)$ 枚举是否有马选择 ，选了多少个 $(3,1,2)$ 和 $(5,1,0)$ ，就变成了不用考虑大圈的情况。我们设现在还有 $n$ 匹马没有用，还剩 $A$ 次过河和 $C$ 次小圈， $c_{i,j}$ 表示用 $i$ 匹马，过了至少 $j$ 次河最多能跑几次小圈， $a_{i,j}$ 表示用 $i$ 匹马，跑了至少 $j$ 次小圈最多能过几次河，那么答案只有三种情况：

$$\min\{\max_{j\geq A} c_{n,j}\}+A $$

$$\min\{\max_{j\geq C} a_{n,j}\}+C $$

$$\max_{j< A,c_{n,j}<C} j+c_{n,j} $$

dp 预处理之后可以离线用 $\log$ 数据结构维护得到上述值。

复杂度 $\mathcal{O}(n^2\log m+nm)$ 。

简单做法，设 $f_{i,j,k}$ 表示第一个条件满足 $i$ 个，第二个条件满足 $j$ 个，第三个条件满足 $k$ 个至少需要多少匹马， $\mathcal{O}(m^3)$ 。

码

const int N = 310;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m, a, b, c, ans;
	int f[N][N][N];

	int main() {
		n = Read(), m = Read(), a = Read(), b = Read(), c = Read();
		for (int i = 0; i <= a; i++) {
			for (int j = 0; j <= b; j++) {
				for (int k = 0; k <= c; k++) {
					if (!i && !j && !k) continue;
					f[i][j][k] = 1e9;
					for (int o = 0; o * 50 < 100 && o <= i; o++) {
						for (int p = 0; o * 50 + p * 20 < 100 && p <= j; p++) {
							for (int q = 0; o * 50 + p * 20 + (1 << q) <= 100 && q <= k; q++) {
								if (!o && !p && !q) continue;
								f[i][j][k] = min(f[i][j][k], f[i - o][j - p][k - q] + 1);
							}
						}
					}
					if (f[i][j][k] <= n) ans = max(ans, i + j + k);
				}
			}
		}
		printf("%d", ans);
		return 0;
	}
}

int main () {
	freopen("horse.in", "r", stdin);
	freopen("horse.out", "w", stdout);
	Main::main();
	return 0;
}