• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

【DP】Loj – 「JOI Open 2016」摩天大楼

开发技术 开发技术 3小时前 2次浏览

题意:传送门

(text{我的做法:})

看到排列,状压?哦数据范围不对。然后又放飞自我,去想建图啊容斥啊等等。

最后还是瞄了一眼标签:DP 。然后又想到了以前的一个套路。

首先原式子的绝对值可以看做是 相邻两个数的 (max – min)

然后那个套路就是将序列 (a) 排好序,考虑依次插入,这样就能消掉 max,min 这种烦人的东西。

DP过程可以看做是维护一堆连通块,插入一个数要么连接两个连通块,要么自己新建一块,要么挨着先前的块。

问题是怎么在DP过程中算费用,这个考虑预测DP(写写式子就懂了)。

但是在最左边和最右边的块很特殊,有个边界,要记一下。

于是就有了巨垃圾的DP:设 (f[i][j][k][0/1][0/1]) 表示前 (i) 个数共构成了 (j) 个连通块,当前费用为 (k) ,左/右边界是否已确定的方案数。

开始我算错复杂度,以为费用在DP过程中的范围只能是 ([-10000,1000]) ,然后 1e8 卡卡常,滚动下数组能过 没想到真的过了

然而写这篇文章时才发现 (a_i le 1000) ,也就是说费用中途能降到 (-10^5) ……,只要出最大的那100个数就能卡死我,这题数据水了。。。

(text{Solution:})


程序员灯塔
转载请注明原文链接:【DP】Loj – 「JOI Open 2016」摩天大楼
喜欢 (0)