分治优化决策单调性
<!--more--> 分治优化决策单调性 在我们了解的DP方程中，经常会有$f[i]=sum_{max}/sum_{min}/min/max{f[j]+calc(i,j)}$，并且calc(i,j)满足四边形不等式，这种方程存在，而通常情况下，calc(i,j)可以非常轻松的得出，比如...
决策单调性优化dp
决策单调性： 对于一些dp方程，经过一系列的猜想和证明，可以得出，所有取的最优解的转移点（即决策点）位置是单调递增的。 即：假设f[i]=min(f[j]+b[j]) (j<i) 并且，对于任意f[i]的决策点g[i]，总有f[i+1]的决策点g[i+1]>=g[i](或者<=g[...
[NOI2009]诗人小G --- DP + 决策单调性
[NOI2009]诗人小G 题目描述： 小G是一个出色的诗人，经常作诗自娱自乐。 但是，他一直被一件事情所困扰，那就是诗的排版问题。 一首诗包含了若干个句子，对于一些连续的短句，可以将它们用空格隔开并放在一行中，注意一行中可以放的句子数目是没有限制的。 小G给每首诗定义了一个行标准长度（行的长度为一...
决策单调性优化
BZOJ1563 #include <cstdio>#include <cmath>#include <cstring>#include <iostream>#define LDB long doubleusing namespace std; ...
决策单调性 dp
对于一些具有决策单调性的dp题目，我们可以应用斜率优化将复杂度从O（n^2）降到O（n）。 bzoj1010 HNOI2008 玩具装箱toy 题目大意：对于一些一维长度的物品，我们可以将连续的i~j个物品放在一起，费用是（j-i+sigma lk（i<=k<=j）-L）^2，求n个物品...
洛谷P1973 [NOI2011]Noi嘉年华（决策单调性）
传送门鉴于FlashHu大佬讲的这么好（而且我根本不会）我就不再讲一遍了->传送//minamoto#include<iostream>#include<cstdio>#include<algorithm>#defineupd(A,L,R){cmax(A[i...
洛谷P1973 [NOI2011]Noi嘉年华（动态规划，决策单调性）
洛谷题目传送门DP题怕是都要大大的脑洞。。。。。。首先，时间那么大没用，直接离散化。第一问还好。根据题意容易发现，当一堆活动的时间有大量重叠的时候，更好的办法是把它们全部安排到一边去。那么我们转移的时候也肯定是要一块一块地转移啦。设\(tot_{l,r}\)为完全被包含在\(l-r\)时间内活动总数...