qbxt Day3 其余题

时间:2021-06-13 23:26:27

例题1

noiopenjudge9277

给出在最底层的木头的个数,问有多少种堆放木头的方式,当然你的堆放方式不能让木头掉下来.

在堆放的时候木头必须互相挨着在一起.

设dp[i]表示多少个log(原木)为底时的方案数。

dp[i]=dp[1](i-1)+dp[2](i-2).....dp[i-1]*1

这就是dp方程,不过好像是O(n^2)的,过不了

我们再看看看dp[i+1]

dp[i+1]=dp[1]i+dp[2](i-1).....dp[i]*1

发现dp[i+1]是dp[i]加上1~i dp值的和

然后使用前缀和,就可以O(n)处理


例题2

hdu4362

在连续的 n 秒中,在x轴上每秒会出现 m 个龙珠,出现之后会立即消失,知道了第0秒所在的位置,每从一个位置i

移动到另一个位置j的时候,消耗的价值为abs(i-j), 拿到龙珠也要消耗一个价值(不同龙珠的价值不同),问 n 秒之后最少消耗多少价值。

dp最基础的o(nm^2)很好想

我们考虑优化

abs很难看,我们拆开他,就是左起一次dp,右起一次dp,取最小值。

然后我们设一个数s,表示当前可以从s这个最优状态中转移

s如何求。我们只需要比较挖出上一个龙珠的价值加上和跑过来的价值,和单挖当前龙珠的价值就可以了。


例题3

hdu5009

给你一个数组,每个值代表一种颜色,每次选一个区间涂颜色,代价是区间内颜色种类数的平方,涂完所有数组,问你最小代价是多少。

o(n^2) 的dp很好想,然是我们仍然过不去2333.我们还是需要考虑加速

我们想一下,如果有数量相同种颜色的长度不同,右端点相同的区间,我们肯定是选长的。显而易见的贪心。

然后我们考虑记录每个颜色最晚的出现位置并维护(类似扫描)

用一个链表,每次按着颜色网后跳,最多跳\(\lfloor \sqrt{n} \rfloor\)次,时间复杂度就是O(\(n \sqrt{n}\));

对于五万的数据就是可以过了了。