脚本宝典收集整理的这篇文章主要介绍了DP水题乱作，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

George and Job

设 (f_{i,j}) 表示前 (i) 数选了 (j) 个区间。

不难得出转移方程 (f_{i,j}=max(f_{i-m,j-1}+sum[i]-sum[i-m-1]))。

其实前四道题都可以秒

Star sky

因为 (c) 最大为 (10)，我们考虑将时间按 (mod c) 分类，可以发现同一类的答案都是类似的。

我们对于每一个 (t in [0,c-1])，求一遍二维前缀和即可。

New Year and Domino

我们考虑将可以放一个骨牌的点打上标记，做二维前缀和，但还要考虑边界情况，把骨牌出界的情况减去即可。

Coloring Trees

首先我们肯定想状态，考虑前 (i) 个树分成了 (j) 段，就有一个初步状态 (f_{i,j})，但是我们还要用颜色来考虑分段数，所以还要记录一个颜色 (k)，最终状态就是 (f_{i,j,k})。

我们分两种情况。

• 如果这个点没有颜色，那么我们先考虑前面一个点和它颜色相同的情况，即 (f_{i,j,k}=min(f_{i,j,k},f_{i-1,j,k}+p_{i,k}))，在考虑不同的情况，即 (f_{i,j,k}=min(f_{i,j,k},f_{i-1,j-1,t}+p_{i,t}))。
• 如果这个点有颜色，那么我们还是考虑前面一个点颜色是否和它相同，如果前面一个点没有颜色，即 (f_{i,j,k}=min(f_{i,j,k},f_{i-1,j-1,t}+p_{i,t})(t!=k), f_{i,j,k}=min(f_{i,j,k},f_{i-1,j,k}+p_{i,k}))。 否则就判断前面一个点颜色是否相同，相同就 (f_{i,j,k}=min(f_{i,j,k},f_{i-1,j,k}))，不同就 (f_{i,j,k}=min(f_{i,j,k},f_{i-1,j-1,c_{i-1}} ))。

消失之物

一个显然的背包。

少一个物品？我们先做一遍普通背包，然后把少的那个物品去掉不就好了？

「NOIP2016」换教室

最裸的暴力就是枚举换的课程，然后算答案，大概是 (O(n^3)) 的。

怎么办？

设 (f_{i,j,0/1})，表示前 (i) 个课换了 (j) 次，(0/1) 表示 (i) 是否换。

我们定义 (v_{1}=c_{i},v_{2}=d_{i},v_3=c_{i-1},v_4=d_{i-1})。

大家都知道期望长度等于概率乘上路径长度，那么就有:

只是难写，思路真的简单。

[CCO2021] bread First SeArch

给定一个图，添加最少的边使得它的 bfs 序为 (1)~(n)。

啥也不会？我们试着 DP。

定义 (f_{i}) 表示 (1)~(i) 子图的答案。

我们可以初步得出一个转移方程：

(val(j,i)) 表示 ((j+1)) ~ (i) 中与 (1)~(j) 有边的节点数。

为什么呢？

附一张图：

如果我们什么都不加，肯定会先访问 5 号节点。

所以我们连一条 (3 to 5) 是不是可以了？

那为啥那么要有 (forall u in [i,n] 与 forall v in [1,j] 没有连边) 这个条件呢？

假设 (i=4,j=5)。

例如这种情况：

你会发现 4,5 如何连边都没有用。

你会发现你根本不需要连边。

大概就上面两种情况。

如果直接计算，这是 (O(n^3)) 的。

我们设 (s_{i,j}) 表示 (1)~(i) 和 (1)~(j) 有边的节点个数。

你可以在 (O(n^2)) 的时间内预处理出 (s)。

具体就是把 (i-1) 的 (s) copy 过来，然后把与 (i) 有边的 (j) 的 (s_{i,j}) 加上成 (1)。

然后 (val(i,j)=s_{i,i}-s_{i,j}+j-i)。

那么如何优化？

考虑 (s_{i,j}) 的预处理，其实就是在 (s_{i-1,j}) 的基础上改改，我们可以用主席树优化。

至于后面的 DP，打表可知它满足决策单调性，队列优化即可。

@R_826_1304@ (O(nLOGn))。

脚本宝典总结

以上是脚本宝典为你收集整理的DP水题乱作全部内容，希望文章能够帮你解决DP水题乱作所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。