由于该题的数据规模很小,并且搜索空间也在可接受范围内,因此可以考虑搜索解答。
搜索过程中,枚举当前采矿点选择哪一块候选晶体,并记录每种能量晶体的持有数量。之后逐层往下搜,直到所有采矿点处理完毕,更新答案。再回溯时,将上次选择的候选晶体对应类型计数减一,并再次选择其它候选晶体即可。
一位探索者将依次经过 n 个采矿点,共有 m 种能量晶体。每到一个采矿点,他可以从三块候选晶体中恰好选择一块带走。第 i 个采矿点的第 j 块候选晶体拥有基础价值 xi,j,并且属于第 ti,j 种能量晶体。
如果某次选择后,某一种能量晶体的持有数量恰好首次达到 3 块,探索者会获得一次该种类的共鸣加成 rp。每种能量晶体的共鸣加成最多获得一次。
探索者希望求出经过全部采矿点后,能够获得的最大总价值。
约束:
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册