「AHOI / HNOI2018」道路

2018-4-13模拟赛:道路
原本是最水的一题又因为题目啰嗦,题序不对好像当场只有两人A掉了呢。
但是这题的确很水,可惜我当场也是没想出来。
这题就是记忆化搜索啦!
我们用f[k][x][y]代表现在第k个节点,翻修x条公里,翻修y条铁路的最小代价,然后记忆化一下之后状态转移
f[k][x][y]=min(f[lc][x][y]+f[rc][x][y+1],f[lc][x+1][y]+f[rc][x][y]),lc,rc分别代表左右子树节点的编号。 ......  查看更多

[HNOI2002]营业额统计

[HNOI2002]营业额统计
这题,其实就是伸展树裸题嘛。
就是找前驱后继,我们主要还是维护一颗伸展树,然后慢慢慢慢插点,然后找前驱后继就好了。
但是这里的前驱后继是可以相等的,所以我们要找x+1的前驱,x-1的后继,然后就好了呀。
留个坑用set其实好像也可以做,真的我很想试试但是懒。 ......  查看更多