2017-05-27
【bzoj 4774】修路

这个好像就是板子题的样子。

但又没有板子的那么过分, 还有一点子集dp的小trick ?

好吧, 它就是个板子题。

阅读此文

2017-05-24
【bzoj 2244】[SDOI2011]拦截导弹

cdq分治优化dp的题目, 不是很了解当时省选这个题目的得分情况。

不过感觉对于日益简单SD一轮, 这个题目放在现在算是难度适中。

比较好写的一个题目。

阅读此文

2017-05-05
【bzoj 2063】我爸是李刚

这个题目Yveh送给xyx做胡策题的, 但是我这种只做过二进制数位dp裸题的丝薄选手, 直接懵逼了好不好。。

实际上是数位dp的例题, 好几年前的论文里就有了。

话说这个题目真是非常的魔性。

阅读此文

2017-05-03
【bzoj 4008】[HNOI2015]亚瑟王

是一个概率期望相关的题目, 但并没有使用期望的线性性质或者\(f[S]=\sum (f[T]+v_{S \to T}) \times p_{S \to T}\) 这类常见的dp思路。

这个题目是从期望的定义出发, 也就是求出概率再乘权值得到期望。

阅读此文

2017-05-01
【bzoj 4011】[HNOI2015]落忆枫音

这个题目感觉还是比较奇妙的, 虽然难度不是很大

做法主要还是一个拓扑图上的dp, 因为新图只是在原图(有向无环图)上添加了一条边, 所以做法肯定还是从有向无环图中拓展出来的。

比较重要的一个idea就是\(\text{ans}=\text{sum}-\text{illegal}\)

阅读此文

2017-04-29
【bzoj 3742】Painting

一道国家集训队好几年前的互测题, 现场似乎被当做送分题? 我是在XYM屠历年集训队题目的时候发现自己碰巧会做?

想我这样的菜鸡, 肯定只是碰巧好吧。 而且看我的常数那么大, 一定是人傻QWQ

阅读此文

2017-01-01
【bzoj 3652】大新闻

经典的数位DP题目?

阅读此文

2017-01-01
【bzoj 4543】[Poi2014]Hotel

一道精妙的树链剖分优化DP的题目

阅读此文