数学考试
时间限制：1 秒 空间限制：64M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！ 
题目描述
牛妹参加了 2022 年普通高校全牛世界招生统一考试。数学试题太难，她决定复读。
为了在考试中取得更好的成绩，牛妹决定对数学进行特训。特训练习共
n
n
n 道题，第
i
i
i 题的难度为
a
i
a_i
ai，分值为
b
i
b_i
bi。为了更好提高自己的数学水平，牛妹决定按照题目顺序做题。
做题会对牛妹的压力指数
P
P
P 产生影响。牛妹在长期磨练中养成了一颗大心脏，做完第
i
i
i 题后，牛妹可以选择保持自己的压力指数
P
P
P 不变、使
P
P
P 增加
Q
i
Q_i
Qi 或使
P
P
P 减少
W
i
W_i
Wi。压力指数上限为
K
K
K，下限为
0
0
0。如果
P
P
P 增加
Q
i
Q_i
Qi 后大于
K
K
K，牛妹就不可以选择让自己的压力指数增加
Q
i
Q_i
Qi；同理，如果
P
P
P 减少
W
i
W_i
Wi 后小于
0
0
0，牛妹就不可以选择让自己的压力指数减少
W
i
W_i
Wi。
牛妹相信压力可以转化为动力。当牛妹在压力为
P
P
P 的状态下完成第
i
i
i 题时，她一定可以做对这一题，并可以积累
a
i
×
P
a_i \\times P
ai×P 的经验。但压力太大会反噬牛妹，当
P
>
b
i
P > b_i
P>bi 时，牛妹不能做对第
i
i
i 题，无法积累任何经验。请注意，无论是否做对，都算作完成了第
i
i
i 题，在做完后，才更改压力值。
牛妹想要知道，完成本次数学特训后，她最多可以积累多少经验。牛妹初始的压力值可以由牛妹在
0
−
K
0 – K
0−K 范围内自由选定。
请注意，本题的空间限制较为特别，仅有 64MB。
输入描述
输入共
n
+
1
n + 1
n+1 行。
- 输入的第一行为两个正整数
n
,
K
n, K
n,K，1
≤
n
≤
10
4
1 \\le n \\le 10^4
1≤n≤104，1
≤
K
≤
5
×
10
3
1 \\le K \\le 5 \\times 10^3
1≤K≤5×103。 - 接下来
n
n
n 行，每行四个正整数，第i
+
1
i + 1
i+1 行分别为a
i
(
1
≤
a
i
≤
10
2
)
a_i\\ (1 \\le a_i \\le 10^2)
ai (1≤ai≤102)，b
i
(
1
≤
b
i
≤
10
9
)
b_i\\ (1 \\le b_i \\le 10^9)
bi (1≤bi≤109)，Q
i
(
1
≤
Q
i
≤
K
)
Q_i\\ (1 \\le Q_i \\le K)
Qi (1≤Qi≤K)，W
i
(
1
≤
W
i
≤
K
)
W_i\\ (1 \\le W_i \\le K)
Wi (1≤Wi≤K)。
输出描述
输出共一行，为牛妹可以积累经验的最大值。
示例 1
输入：
4 10
1 100 1 1
2 100 1 1
3 100 1 1
4 100 1 1
输出：
100
数据范围与提示
-
1
≤
n
≤
10
4
1 \\le n \\le 10^4
1≤n≤104，1
≤
K
≤
5
×
10
3
1 \\le K \\le 5 \\times 10^3
1≤K≤5×103 -
1
≤
a
i
≤
10
2
1 \\le a_i \\le 10^2
1≤ai≤102，1
≤
b
i
≤
10
9
1 \\le b_i \\le 10^9
1≤bi≤109，1
≤
Q
i
,
W
i
≤
K
1 \\le Q_i, W_i \\le K
1≤Qi,Wi≤K - 核心思路：动态规划 + 滚动数组。
- 设
d
p
[
p
]
dp[p]
dp[p] 表示做完全部前若干题、当前压力为p
p
p 时可积累的最大经验。初始时因压力可自由选定，d
p
[
p
]
=
0
dp[p] = 0
dp[p]=0 对所有p
∈
[
0
,
K
]
p \\in [0, K]
p∈[0,K] 成立。 - 处理第
i
i
i 题时，先用本题的收益更新：d
p
′
[
p
]
=
d
p
[
p
]
+
{
a
i
×
p
,
p
≤
b
i
0
,
p
>
b
i
dp'[p] = dp[p] + \\begin{cases} a_i \\times p, & p \\le b_i \\\\ 0, & p > b_i \\end{cases}
dp′[p]=dp[p]+{ai×p,0,p≤bip>bi 再考虑“做完后修改压力”，即新状态p
p
p 可以由上一题的p
p
p（不变）、p
−
Q
i
p – Q_i
p−Qi（增加压力）、p
+
W
i
p + W_i
p+Wi（减少压力）转移而来，注意转移来源需满足p
−
Q
i
≥
0
p – Q_i \\ge 0
p−Qi≥0 与p
+
W
i
≤
K
p + W_i \\le K
p+Wi≤K 的合法性。 - 最终答案为
max
0
≤
p
≤
K
d
p
[
p
]
\\max_{0 \\le p \\le K} dp[p]
max0≤p≤Kdp[p]。 - 空间复杂度
O
(
K
)
O(K)
O(K)，时间O
(
n
K
)
=
5
×
10
7
O(nK) = 5 \\times 10^7
O(nK)=5×107，刚好适配 64MB 的严格空间限制（不可开二维数组）。 - 经验最大值可达
100
×
5000
×
10
4
=
5
×
10
9
100 \\times 5000 \\times 10^4 = 5 \\times 10^9
100×5000×104=5×109，需使用 64 位整数（long long）存储。
解题思路
本题是动态规划 + 滚动数组优化的经典问题。牛妹按顺序做题，每道题有一个难度
a
i
a_i
ai、阈值
b
i
b_i
bi、压力增加量
Q
i
Q_i
Qi 和压力减少量
W
i
W_i
Wi。压力
P
P
P 的初始值可在
[
0
,
K
]
[0, K]
[0,K] 内自由选择。每做完一题，若当前压力
P
≤
b
i
P \\le b_i
P≤bi，则获得
a
i
×
P
a_i \\times P
ai×P 的经验，否则获得
0
0
0 经验；之后可以选择保持压力、增加
Q
i
Q_i
Qi 或减少
W
i
W_i
Wi（需满足压力始终在
[
0
,
K
]
[0, K]
[0,K] 内）。目标是最大化总经验。
由于
n
≤
10
4
n \\le 10^4
n≤104，
K
≤
5000
K \\le 5000
K≤5000，状态数为
O
(
K
)
O(K)
O(K)，但直接开二维数组会超出 64MB 空间限制，因此必须使用滚动数组，只保留上一题结束后的压力状态。
1. 问题等价转化
- 设 dp[p] 表示处理完当前题目后，压力值为
p
p
p 时能积累的最大经验。 - 初始时，牛妹可以自由选择初始压力，因此对于所有
p
∈
[
0
,
K
]
p \\in [0, K]
p∈[0,K]，dp[p] = 0。 - 对于每道题
(
a
i
,
b
i
,
Q
i
,
W
i
)
(a_i, b_i, Q_i, W_i)
(ai,bi,Qi,Wi)： - 计算本题经验：对于每个可达的压力
p
p
p，若p
≤
b
i
p \\le b_i
p≤bi，则本题获得经验a
i
×
p
a_i \\times p
ai×p；否则获得0
0
0。将经验累加到当前状态上，得到临时值 c = dp[p] + (p <= b_i ? a_i * p : 0)。 - 选择压力变化：做完本题后，牛妹可以选择压力不变、增加
Q
i
Q_i
Qi 或减少W
i
W_i
Wi（需满足新压力在[
0
,
K
]
[0, K]
[0,K] 内）。用临时值 c 更新新压力对应的状态：- 压力不变：new_dp[p] = max(new_dp[p], c)
- 增加压力：若
p
+
Q
i
≤
K
p + Q_i \\le K
p+Qi≤K，则 new_dp[p + Q_i] = max(new_dp[p + Q_i], c) - 减少压力：若
p
−
W
i
≥
0
p – W_i \\ge 0
p−Wi≥0，则 new_dp[p – W_i] = max(new_dp[p – W_i], c)
- 处理完所有题目后，答案即为 max(dp[0..K])。
2. 算法实现
n
,
K
n, K
n,K。
K
+
1
K+1
K+1 的 long long 数组 f 和 g，f 初始全为
0
0
0（表示初始状态任意压力经验均为
0
0
0），g 用于暂存下一状态。
- 读入
a
,
b
,
q
,
w
a, b, q, w
a,b,q,w。 - 将 g 全部置为
−
1
-1
−1（表示该状态尚未被更新，也可用极小值）。 - 遍历压力
x
x
x 从0
0
0 到K
K
K：- 令 c = f[x]。
- 若
x
≤
b
x \\le b
x≤b，则 c += a * x。 - 更新 g[x] = max(g[x], c)。
- 若
x
+
q
≤
K
x + q \\le K
x+q≤K，更新 g[x + q] = max(g[x + q], c)。 - 若
x
−
w
≥
0
x – w \\ge 0
x−w≥0，更新 g[x – w] = max(g[x – w], c)。
- 将 f 与 g 交换（或 f = g）。
3. 复杂度分析
- 时间复杂度：每道题需要遍历
K
+
1
K+1
K+1 个压力状态，共n
n
n 道题，总复杂度O
(
n
K
)
=
10
4
×
5000
=
5
×
10
7
O(nK) = 10^4 \\times 5000 = 5 \\times 10^7
O(nK)=104×5000=5×107 次操作，在 1 秒内可以完成。 - 空间复杂度：仅使用两个长度为
K
+
1
K+1
K+1 的数组，空间为O
(
K
)
O(K)
O(K)，远小于 64MB 限制。
总结
通过滚动数组将二维 DP 压缩为一维，每次用上一题的状态推导当前题的状态。核心在于先计算本题经验，再决策压力变化。初始压力自由选择，因此初始 DP 全为
0
0
0。注意使用 long long 防止经验值溢出。
代码简要说明
- 数组 f 和 g：f 存储上一轮结束后的最优经验，g 用于生成新一轮状态。
- 循环处理每道题：
- fill(g.begin(), g.end(), -1) 重置 g。
- 遍历所有可能的压力 x，计算本题经验 c。
- 分别更新压力不变、增加、减少三种情况到 g 中。
- f.swap(g) 交换数组，进入下一题。
- 输出：遍历 f 取最大值即为答案。
代码内容
#include <bits/stdc++.h>
using namespace std;
#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1e3+10;
const ll INF=1e18;
const ll M=1e6+10;
const ll mod=1e9+7;
int main()
{
ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);
ll n,k;
cin>>n>>k;
vector<ll> f(k+1,0),g(k+1,0);
for(ll i=0;i<n;i++)
{
ll a,q,w;
ll b;
cin>>a>>b>>q>>w;
fill(g.begin(),g.end(),–1);
for(ll x=0;x<=k;x++)
{
ll c=f[x];
if(x<=b) c+=a*x;
if(c>g[x]) g[x]=c;
ll y=x+q;
if(y<=k&&c>g[y]) g[y]=c;
y=x–w;
if(y>=0&&c>g[y]) g[y]=c;
}
f.swap(g);
}
ll ans=0;
for(ll p=0;p<=k;p++) if(f[p]>ans) ans=f[p];
cout<<ans<<'\\n';
return 0;
}
