【考前冲刺Day6】OI STILE

T1 引子(水箱)

非常简单的模拟题目,错误点有两处:
1. 没有读入多位数字
2. 出现顺序和编号无关

然就是从1号水箱,开始递归,优先从箱底的水管递归下去,然后输出自身的编号。


T2 可爱精灵宝贝

一道区间dp题,考场上写挂了,最后10分钟乱搞居然也有60分,考试完调了一下,有90分实际上是数据太水了

90分代码:

这里区间dp用的是记忆化搜索实现的,dfs中的参数含义如下:

参数名 参数含义
s 第s个精灵
cur 当前时间
sum 当前状态的分数
l 当前状态的左端点
r 当前状态的右端点

其中,l和r指的是按位置排序后精灵序号的左右端点,相当于离散化了坐标

对于状态,我们都有以下选择:
1. 向右走去捕获右边精灵
2. 向右走,虽然捕获不到
3. 向左走去捕获左边精灵
4. 向左走,虽然捕获不到

对于每种状态的遍历,我们就可以算出f[i][j]—选择第i到第j个精灵的最大得分(不一定捕获到了)
答案就是其中最大的

发表评论

电子邮件地址不会被公开。 必填项已用*标注