第一届湖南省信息学拔尖创新挑战活动 总结

第一届湖南省信息学拔尖创新挑战活动 总结

\(100+85+40+40=265\)

拜谢 T4 放水了暴力多给了 \(20\)。可恶 T2 没给初值为极负值而痛失 \(15\)。愤恨 T3 没想到记搜错过正解。

我是 fw,我叫 fw!

Pro.A

简单题,对怪兽的战斗力从小到大排序,按着这个顺序来打怪就行了,可以证明是最优的。

Pro.B

前缀后缀 \(\max\) 整上,枚举中间值,找左右求即可。

注意一开始的初值要赋值为 \(-\infty\) 啊啊啊啊啊啊啊啊啊!!!!!!!1111111111
——来自丢失的 \(15\)pts 的呐喊。

Pro.C

简单记搜。一开始对 \(a\) 数组转个向,然后按顺序搜,边搜边记,\(dp_{i,j}\) 表示当前考虑前 \(i\) 个物品(转向后的)并且目前所占的容量总和为 \(j\),记录选择的物品个数(方便输出)以及上一个的情况 \(pre\),便于后面求解方案情况的时候回退。

注意在输出 \(0\) 的情况下还要多输出一个换行哟~(贼笑)

Pro.D

没听懂。阿拉啦。