黄金限次收益
P5950. 黄金限次收益
场次:2026年10月28日-非AI方向 · 来源:CodeFun2000 P5950
题目描述
一家投资企业准备调整黄金买卖方案,以尽量增加最终利润。企业已经掌握一段时期的逐日报价,可以选择某日购入黄金,并在之后的日期将其出售,通过价差赚取收益。该时期内允许反复买卖,不过每轮交易都有手续费,起始本金也有上限。另外,每次购入的黄金数量相同,完整交易的总轮数不得突破规定额度。
任务:
根据每日报价、起始本金、每轮手续费以及可用交易额度,求出能够实现的最高净利润。
注意:
- 一轮交易必须先购入,再于更晚的日期出售。
- 整个时期内可安排多轮交易,但各轮不得重叠。尚有黄金未售出时,不能再次购入;出售时必须将当前持仓全部清空。
- 每轮由一次购入和一次出售构成,仅在出售时收取一份手续费,且这笔费用与黄金数量无关。
- 此前获利可以补充后续本金。执行购入时,可用现金必须不小于该批黄金的总价,否则该次购入不合法。可以选择全程不交易,最终只统计已经完成买卖的净利润。
输入格式
- 首行给出整数 ,代表已知报价的天数,。
- 次行给出 个以空格分隔的整数 ,按日期顺序表示黄金单价,。
- 第三行给出整数 ,代表完成一轮买卖所收取的费用,。
- 第四行给出整数 ,代表最初可用的现金,。
- 第五行给出整数 ,代表允许完成的买卖轮数上限,。
- 第六行给出整数 ,代表每次必须购入的黄金单位数,。
输出格式
输出一个整数,表示最优方案的净利润,即最终空仓时的现金减去起始本金。若所有可行交易均不能带来正利润,则输出 。
示例
示例 1
输入:
5
8 6 9 3 11
2
12
1
3输出:
22说明: 在第 天购入 单位黄金,需支付 ,本金 足够覆盖费用。
第 天全部售出,收到 ,再扣除手续费 ,这一轮净赚 。
因此最高利润为 。整个方案仅完成 轮买卖,符合额度要求。
示例 2
输入:
7
5 2 6 7 4 9 8
3
4
3
2输出:
14说明: 第 天购入 单位,支付 ,恰好用完本金。
第 天售出,扣费后得到 ,这一轮赚得 ,可用现金变为 。
第 天再购入 单位,需付 ,此时已有现金足以支持。第 天清仓,该轮利润为 。
两轮累计利润为 。
解题思路
输出到底是什么:已完成的买卖带来的净利润
先把「利润」的口径钉死。整笔资金一直待在账户里,起始有 ,中途每一轮买进花掉 、卖出收到 、卖出时再扣 ,最后要求空仓。于是最终现金是
而题目要的净利润就是这个和:
两条推论直接影响后面的状态设计:
- 单轮的收益只取决于买入日与卖出日的价差,与当时手里有多少钱无关。买卖的数量恒为 ,手续费恒为 ,一轮要么赚要么亏,金额是固定的。
- 宏观上看,选方案就是挑若干组「买日 < 卖日 」,组与组之间不重叠(卖完才能再买),组数不超过 。目标是把这些组的收益加起来最大。
题面又规定「若所有可行交易均不能带来正利润,则输出 」,所以答案要在最终结果上做一次 —— 空仓不交易永远是一个合法方案。
一条价格上藏着的约束:买入时必须付得起
如果只有价差,那就成了「在序列上挑 个不重叠的上升段」的纯贪心。真正把难度抬起来的是这句:
执行购入时,可用现金必须不小于该批黄金的总价。
因为本金 有限,某些看起来很赚的买入其实做不了。示例 1 里前两天报价 与 ,买 单位要 与 ,而本金只有 —— 贵得买不起;只有第 天的 才付得起。
于是「选哪些轮」不能脱离「当时还剩多少钱」独立决定,而这又正好是状态的定义之处:现金 = 已实现利润,已实现利润是唯一需要携带的现金信息。
状态:完成 轮、空仓时的最大利润
按天推进。定义
「空仓」是必须写进状态的前提:题面不允许持仓时再买入,所以任何时刻只有两种可能 —— 手里没货(可以买、也可以什么都不做),或者手里有货(只能等卖)。 只管前一种。
状态能这样压缩,靠的是一条支配关系:同样的轮数下,利润更多的人一定不比利润少的人差。他能买得起的东西只多不少,能赚到的钱也只多不少。所以每个 只需要保留最大值,丢掉其余。
一天里有两种事会发生,于是两条转移:
for a in price: # 逐日推进
cur = dp[:] # 今天什么都不做
for r in range(1, k_max + 1):
if best_buy[r - 1] != NEG:
cand = best_buy[r - 1] + a * qty - fee # 今天卖出,结束第 r 轮
if cand > cur[r]:
cur[r] = candcur[r] 一开始拷贝自 dp[r],表示这一天既没买也没卖;卖出的候选值来自下面要讲的 best_buy。
把「买入价」折进一个辅助量
按上面的转移,卖出时需要知道「这一轮是什么价位买的」,可 里并没有这个信息。若把它也塞进状态,状态就成了 种买入价,复杂度立刻失控。
换个角度:卖出那天的收益是
括号里的部分只跟买入日有关,跟卖出日无关。于是可以对每个 维护一个「历史最优买入」:
卖出时直接查表, 拿到最优的那次买入。登记今天的买入就一行:
for r in range(k_max):
if dp[r] != NEG and cash + dp[r] >= a * qty: # 买得起:本金 + 已赚利润
val = dp[r] - a * qty
if val > best_buy[r]:
best_buy[r] = val
dp = cur注意条件写的是 cash + dp[r] >= a * qty:净利润 dp[r] 要加回起始本金 ,才是此刻手里的现金。
一天之内的顺序:先结算卖出,再登记买入
上面两段代码的先后不能颠倒,原因是题面那句「一轮交易必须先购入,再于更晚的日期出售」。
- 算
cur时用的是旧的best_buy,里面只登记了今天以前的买入 —— 今天买、今天卖凑不出合法的一轮; - 登记今天的买入时用的是旧的
dp(今天开盘前的状态,也就是昨天收盘的状态),而不是刚算出的cur。如果用了cur,等于允许把今天卖出赚到的钱立刻再投进去,并且同一天再卖一次。
dp = cur 放在最后,一天只推进一次。
实现落点
NEG = float("-inf")标记「这个轮数还不可达」,让max直接跳过;dp[0] = 0:零轮、零利润,从第一天开盘就成立;- 每天先拷贝
cur = dp[:],就是「今天什么都不做」这条转移; - 卖出只遍历 (第 轮需要前 轮的成绩做基础),买入只遍历 (买完这一轮最多用到 );
- 收尾
print(max(0, max(dp)))同时处理「可以不做交易」和「所有交易都亏」。
完整代码实现
"""
P5950. 黄金限次收益 - 按天推进、轮数做维度的 DP
有 N 天报价 a[i],起始本金 C,每轮手续费 F,最多 K 轮,
每轮买入并卖出固定 Q 单位(卖出时收一次 F,买入时现金必须够付)。
求最终空仓时的最大净利润,非正则输出 0。
输入格式:
- 第 1 行:N
- 第 2 行:N 个整数,日报价
- 第 3 行:F(每轮手续费)
- 第 4 行:C(起始本金)
- 第 5 行:K(轮数上限)
- 第 6 行:Q(每轮固定数量)
输出格式:
- 一个整数:最大净利润(不小于 0)。
核心思路:
dp[r] = 今天收盘、恰好完成 r 轮、空仓时的最大利润。
同一轮数下利润越大越不会更差,所以每个 r 只留最大值。
卖出的收益只跟买入日有关,把 (dp[r] - 买入价*Q) 的最大值记进 best_buy[r],
卖出时 O(1) 查到最优买入;买入时要求 C + dp[r] >= 买入价*Q。
每天先结算卖出(用旧 best_buy),再登记买入(用旧 dp),保证不同日成交。
时间复杂度:O(N * K)
空间复杂度:O(K)
"""
# https://codefun2000.com/p/P5950
import sys
NEG = float("-inf")
# @sample-start
"""
样例输入 1:
5
8 6 9 3 11
2
12
1
3
样例输出 1:
22
"""
# @sample-end
# @sample-start
"""
样例输入 2:
7
5 2 6 7 4 9 8
3
4
3
2
样例输出 2:
14
"""
# @sample-end
def solve():
data = sys.stdin.buffer.read().split()
if not data:
return
p = 0
n = int(data[p]); p += 1
price = [int(x) for x in data[p:p + n]]; p += n
fee = int(data[p]); p += 1
cash = int(data[p]); p += 1
k_max = int(data[p]); p += 1
qty = int(data[p])
dp = [NEG] * (k_max + 1)
dp[0] = 0 # 0 轮、0 利润
best_buy = [NEG] * (k_max + 1) # best_buy[r] = max(dp[r] - 买入价*Q)
for a in price:
cur = dp[:] # 今天什么都不做
for r in range(1, k_max + 1):
if best_buy[r - 1] != NEG:
cand = best_buy[r - 1] + a * qty - fee # 今天卖出,第 r 轮结束
if cand > cur[r]:
cur[r] = cand
for r in range(k_max):
# 买得起:手里的现金 = 本金 + 已实现利润
if dp[r] != NEG and cash + dp[r] >= a * qty:
val = dp[r] - a * qty
if val > best_buy[r]:
best_buy[r] = val
dp = cur
print(max(0, max(dp)))
def run_tests():
"""运行嵌入的示例与边界用例,方便本地自测。"""
import io
cases = [
("5\n8 6 9 3 11\n2\n12\n1\n3\n", "22"),
("7\n5 2 6 7 4 9 8\n3\n4\n3\n2\n", "14"),
# 一路下跌:最好的选择是全程不交易
("3\n9 5 1\n1\n100\n2\n1\n", "0"),
# 买得起、但价差不够手续费:同样输出 0
("2\n10 11\n5\n100\n1\n1\n", "0"),
# 轮数足够时抓住深坑:4 -> 10 与 1 -> 20 各赚一笔,胜过一路持有
("4\n4 10 1 20\n1\n10\n5\n1\n", "23"),
]
for i, (inp, expected) in enumerate(cases, 1):
old_stdin, old_stdout = sys.stdin, sys.stdout
sys.stdin = io.TextIOWrapper(io.BytesIO(inp.encode("utf-8")))
sys.stdout = io.StringIO()
try:
solve()
output = sys.stdout.getvalue().strip()
finally:
sys.stdin, sys.stdout = old_stdin, old_stdout
status = "✓" if output == expected else "✗"
print(f"用例 {i}: 期望={expected!r}, 实际={output!r} {status}")
if __name__ == "__main__":
if len(sys.argv) > 1 and sys.argv[1] == "--test":
run_tests()
else:
solve()示例推演
示例 1:,报价 ,本金 ,,
只有一轮,dp 只有 两格。每天先看能不能买,再看能不能卖。
| 天 | 报价 | 买 单位需 | 现金 | 买得起 | 卖出候选 | |
|---|---|---|---|---|---|---|
| 否 | — | |||||
| 否 | — | |||||
| 否 | — | |||||
| 是 | — | |||||
| 否 |
第 天登记买入:best_buy[0] = dp[0] - 3*3 = 0 - 9 = -9。第 天卖出:。
答案 ,与官方一致。注意前三天不是「价格不好」,而是本金不够:第 天 ,这条路径在示例里根本不存在。
示例 2:,报价 ,本金 ,,,
买入成本是 ,逐日表如下(best_buy[r] 表示「已用 轮、该买入价对应的价值」):
| 天 | 报价 | 买 单位需 | 现金 | ||||
|---|---|---|---|---|---|---|---|
| — | — | ||||||
| — | |||||||
| — | |||||||
| — | |||||||
挑三行细看:
- 第 天: 正好等于本金,买得起,
best_buy[0] = 0 - 4 = -4; - 第 天:用第 天的买入卖出,,这是「一次买卖赚 」的另一种写法;第 天自己买不起(需 ,现金只有 );
- 第 天:,现金 ,于是
best_buy[1] = 7 - 8 = -1。第 天卖出得 ,这就是官方的「两轮各赚 ,合计 」。
第 天想再买一轮(,现金 恰好够)也登记了 best_buy[2] = -2,但第 天卖出只有 ,低于已有的 ,不采用。
答案 。它和官方解释里的方案一致:第 天买、第 天卖;第 天买、第 天卖。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 枚举所有「买日/卖日」组合 | 轮就有 对日期,、 时完全不可行 | ||
| 按天推进、轮数做维度(最优) | 每天对 各做一次 转移, |
每天的两次内层循环都是 :一次算「今天卖出」,一次算「今天买入」。空间只有两个长度为 的数组,报价表本身占 。
易错点总结
1. 本金检查漏掉起始现金
把 cash + dp[r] >= a * qty 写成 dp[r] >= a * qty,等于假设账户一开始是空的。示例 1 里 dp[0] = 0 而第 天的买入价是 ,判定「买不起」,于是 best_buy[0] 永远是 、dp[1] 也永远是 ,输出 而不是 ;示例 2 同样输出 而不是 。两组合法的样例直接归零,是这条最典型的症状。
2. 卖出时忘了扣手续费
把 best_buy[r - 1] + a * qty - fee 里的 - fee 删掉,每一轮都多算一份手续费。示例 1 输出 ()而不是 ;轮数多的用例偏得更多,因为漏掉的是「每轮一次」。
3. 收益公式漏乘数量
把 best_buy[r - 1] + a * qty - fee 写成 best_buy[r - 1] + a - fee(买入侧按 扣、卖出侧按 收),单轮收益被算成「一份价差」。示例 1 输出 (,刚好被 兜住,看不出报错)、示例 2 输出 而不是 —— 这类错误在小 上不明显,把 调大才会暴露。