自动搬运

查看原文

来自洛谷，原作者为

	MTFlowCzq 我是心流czq

搬运于2025-08-24 21:15:09，当前版本为作者最后更新于2023-07-12 21:15:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

通过数低？没有题解？那我来写一篇吧（B 题库的题都这么难了？）

题目大意

题目传送门

有 $n$ 场比赛，你准备选不超过 $k$ 场来打，你希望打完以后比赛分最高，初始为 $x$。

你预知了每场比赛打完后的表现分，设打比赛之前的比赛分为 $i$，表现分为 $j$，则打完后比赛分会更新为 $i+\lfloor\frac{j-i}{4}\rfloor$。除此之外，每场比赛有 div1 和 div2 两种类型，div2 的比赛只有在打比赛前的比赛分小于 $1900$ 时才能参与。

写程序求出最高比赛分。

解题思路

先说一句，尽管题目没有明确说，打比赛的顺序是不能调换的（常识好吧），并且别忘了限制了参加场数。

简单的贪心是不凑效的，因为样例已经给出了一组先减分再加分的数据。容易发现难点在于 div 类型的处理。

如果不考虑 div2 限分，那么使用动态规划即可解决问题，令 $f_{i,j}$ 为前 $i$ 场中打 $j$ 场比赛的最高分，那么第 $i+1$ 场比赛可以不打，也可以打了上分（容易发现表现分相同时，初始分越高，打完分数越高），转移方程为：

$$f_{i,j}=\max(f_{i-1,j},x+\lfloor\frac{a_i-x}{4}\rfloor),\ x=f_{i-1,j-1} $$

而在加入类型之后，可以强制下分来打 div2，那么是否可以再维护小于 $1900$ 的最高分呢？思考后会发现难以转移（新的小于 $1900$ 的最高分可能由更小的分数转移得到），这样做似乎不行。一种想法是用 $ok_{i,j,p}=0/1$ 表示前 $i$ 场比赛参加 $j$ 场且分数为 $p$ 的可行性，但这样三维的状态会超时，需要二维的。

经过思考以后，我们发现，可以反过来设计状态，将题目的限制和要求的得分颠倒（经典的 DP 优化手段），变为“要达到一定的分数，至少需要打多少比赛”。于是我们令 $dp_{i,j}$ 为前 $i$ 场比赛中分数恰为 $j$ 时最少的比赛场数。这样，我们就可以用 $dp_{i-1,j}$ 来更新 $dp_{i,j+\lfloor\frac{a_i-j}{4}\rfloor}$ 了，转移式为：

$$dp_{i,x}=\min(dp_{i,x},dp_{i-1,j}+1),\ x=j+\lfloor\frac{a_i-j}{4}\rfloor $$

而对 div2 的比赛，只需加上 $j<1900$ 的限制条件即可。最后找出最大的满足 $dp_{n,j}\le k$ 的 $j$，就是答案。

由于比赛分不会超过 $\max(a_i,x)$，状态数是 $n\max(a_i,x)$，时间复杂度是 $O(n\max(a_i,x))$。由于 $n\le5000$，$a_i,x\le4000$，可以通过本题。

代码

值得一提的是，空间可以使用滚动数组优化，但此时需要注意更新顺序（类似 0-1 背包，每场比赛只能打一次，所以先更新靠近 $a_i$ 的部分）

#include<iostream>
#include<algorithm>
using namespace std;
int n,k,x,dp[4009],id,a;
int main() {
	cin>>n>>k>>x;
	for (int i=0;i<=4000;i++)
		dp[i]=10009; //初设为 INF，大于 n 即可
	dp[x]=0; //一场比赛都不打
	while (n--) {
		cin>>id>>a;
		int m=4000; if (id==2) m=1899; //参与比赛的比赛分限制
		for (int i=a+1;i<=m;i++) { //此处注意两个循环的遍历顺序
			int now=i-(i-a+3)/4; //计算打完后的分数
			dp[now]=min(dp[now],dp[i]+1); //试图更新
		}
		for (int i=min(m,a-1);i>=0;i--) {
			int now=i+(a-i)/4;
			dp[now]=min(dp[now],dp[i]+1);
		}
	}
	for (int i=4000;i>=0;i--)
		if (dp[i]<=k) { //找答案
			cout<<i<<endl; break;
		}
	return 0;
}

---

本人第一篇题解，如有问题和建议欢迎指出！