有人用dw做网站吗,商城类网站设计制作,wordpress 开启模板,php网站开发技术文档文章目录 对于决策单调性的一般解释关于决策单调性的证明四边形不等式一维dp区间dp一种二维dp一些满足四边形不等式的函数类 与图形相结合 决策单调性的常见优化手段二分队列二分栈分治类莫队做法 SMAWKWQS二分WQS多解情况满足四边形不等式的序列划分问题的答案凸性以及WQS二分… 文章目录 对于决策单调性的一般解释关于决策单调性的证明四边形不等式一维dp区间dp一种二维dp一些满足四边形不等式的函数类 与图形相结合 决策单调性的常见优化手段二分队列二分栈分治类莫队做法 SMAWKWQS二分WQS多解情况满足四边形不等式的序列划分问题的答案凸性以及WQS二分的方案构造WQS外层二分时的边界Tips 斜率优化 一些特殊情况 本文与
[学习笔记]斜率优化dp 总结内容相互关联建议放在一起阅读不这样也没事我只是打个广告:) 对于决策单调性的一般解释
众所周知dp中会有转移每一个状态可能会有若干个状态转移而来。现在我们考虑一类较为特殊的dp最优化dp在其中每一个点只能从一个最优状态转移而来。在此基础上如果随着dp顺序的推进每一个点的最优转移点也是单调移动的我们就称其具有决策单调性.
比如说对于一个常见一维 d p : d p i m i n / m a x { d p j w ( j , i ) } dp:dp_imin/max\{dp_jw(j,i)\} dp:dpimin/max{dpjw(j,i)},显然每一个点的dp值只能从 { j ∣ j i } \{j|ji\} {j∣ji}的 d p j dp_j dpj转移而来我们记每一个点 i i i的最优决策转移点为 p i p_i pi.如果我们从1-n遍历i p i p_i pi也随之单调变化那么这个dp就具有决策单调性了.大部分决策单调性体现在决策点单调递增但是也有决策点单调递减的情况(都是建立在枚举的点是从小到大的情况下)
关于决策单调性的证明
显然我们可以打表。只要暴力写一个dp然后毛估估看一看转移点是否单调即可。当然还有其它更加稳妥的方式
该部分讲解如无特殊声明都是建立在求最小化问题的基础上如果要求最大化的话要把对应不等号取反
四边形不等式
一维dp
对应方程形式 F F F : d p i m i n j i { d p j w ( j , i ) } dp_imin_{ji}\{dp_jw(j,i)\} dpiminji{dpjw(j,i)}
我们考虑 p 1 ≤ p 2 ≤ p 3 ≤ p 4 p_1\leq p_2\leq p_3\leq p_4 p1≤p2≤p3≤p4
则最小化情况下的四边形不等式表示为 w ( p 1 , p 3 ) w ( p 2 , p 4 ) ≤ w ( p 1 , p 4 ) w ( p 2 , p 3 ) w(p_1,p_3)w(p_2,p_4)\leq w(p_1,p_4)w(p_2,p_3) w(p1,p3)w(p2,p4)≤w(p1,p4)w(p2,p3)
特别的如果等号永远成立称为四边形恒等式
一般记为交叉 ≤ \leq ≤包含 定理1如果对于dp式F,其w满足四边形不等式则F满足决策单调性 P r o o f : Proof: Proof: 反证法。记 d p i dp_i dpi的最优决策点为 p i p_i pi,假设 y x yx yx且 p x p y p_xp_y pxpy.根据 F F F的定义有 d p x d p p x w ( p x , x ) ≤ d p p y w ( p y , x ) ( 1 ) dp_xdp_{p_x}w(p_x,x)\leq dp_{p_y}w(p_y,x)(1) dpxdppxw(px,x)≤dppyw(py,x)(1) 不难发现 p x p y y x p_xp_yyx pxpyyx,故由四边形不等式 w ( p x , y ) w ( p y , x ) ≤ w ( p x , x ) w ( p y , y ) ( 2 ) w(p_x,y)w(p_y,x)\leq w(p_x,x)w(p_y,y)(2) w(px,y)w(py,x)≤w(px,x)w(py,y)(2) 1 , 2 1,2 1,2两式相加得到: d p p x w ( p x , y ) ≤ d p p y w ( p y , y ) dp_{p_x}w(p_x,y)\leq dp_{p_y}w(p_y,y) dppxw(px,y)≤dppyw(py,y) 则对于 y y y来说 p x p_x px是一个比 p y p_y py更优的决策点与条件矛盾。 故 y x yx yx意味着 p y ≤ p x p_y\leq p_x py≤px单调性得证
区间dp
一般来说高维dp的决策单调性体现在某一个维度相对一维dp来说也会更加难发现但是一种区间dp具有较好的性质
对应方程形式 F F F : d p i , j m i n k i j − 1 { d p i , k d p k 1 , j w ( i , j ) } :dp_{i,j}min_{ki}^{j-1}\{dp_{i,k}dp_{k1,j}w(i,j)\} :dpi,jminkij−1{dpi,kdpk1,jw(i,j)}
这里先介绍一个跟四边形不等式非常像的区间包含不等式考虑 p 1 ≤ p 2 ≤ p 3 ≤ p 4 p_1\leq p_2\leq p_3\leq p_4 p1≤p2≤p3≤p4,则 w ( p 1 , p 4 ) ≥ w ( p 2 , p 3 ) w(p_1,p_4)\geq w(p_2,p_3) w(p1,p4)≥w(p2,p3) 引理1如果对于dp式F其w同时满足四边形不等式以及区间包含不等式则F也满足四边形不等式 P r o o f : Proof: Proof: 我不会但是有人会 定理2如果对于dp式F其满足四边形不等式记 p i , j 为 d p i , j p_{i,j}为dp_{i,j} pi,j为dpi,j的最优决策点则 ∀ i j , p i , j − 1 ≤ p i , j ≤ p i 1 , j \forall ij,p_{i,j-1}\leq p_{i,j}\leq p_{i1,j} ∀ij,pi,j−1≤pi,j≤pi1,j P r o o f : Proof: Proof: 不会1但是有人会
基于此我们对于 F F F就能给出一个复杂度为 O ( n 2 ) O(n^2) O(n2)的优化。
如果在计算 f i , j f_{i,j} fi,j的同时记录 p i , j p_{i,j} pi,j则对决策点 K K K的枚举量为 ∑ 1 ≤ i j ≤ n p i 1 , j − p i , j − 1 ∑ i 1 n p i , n − p 1 , i ≤ n 2 \sum_{1\leq ij\leq n}p_{i1,j}-p_{i,j-1} \sum_{i1}^{n}p_{i,n}-p_{1,i}\leq n^2 ∑1≤ij≤npi1,j−pi,j−1∑i1npi,n−p1,i≤n2
例题
HDU Monkey Party
HDU Tree Construction
大致来说就是看到对应形式证一下四边形不等式包含不等式然后套板子即可
这里给个Monkey Party的代码(幼年码风不喜勿喷)
#includebits/stdc.h
using namespace std;
#define ll long long
const ll N2020;
ll n;
ll mas[N];
ll dp[N][N];
ll s[N][N];
ll sum[N];
ll w(ll l,ll r)
{return sum[r]-sum[l-1];
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);while(cinn){for(int i1;in;i) cinmas[i];for(int i1n;inn;i) mas[i]mas[i-n];for(int i1;inn;i) sum[i]sum[i-1]mas[i];memset(dp,0x3f,sizeof dp);for(int i0;inn;i) dp[i][i]0,s[i][i]i;for(int len2;lenn;len){for(int i1;i2*n-len1;i){int jilen-1;for(int ks[i][j-1];ks[i1][j];k){if(dp[i][j]dp[i][k]dp[k1][j]sum[j]-sum[i-1]){dp[i][j]dp[i][k]dp[k1][j]sum[j]-sum[i-1];s[i][j]k;}}}}ll ans1e17;for(int l1;ln;l){ansmin(ans,dp[l][ln-1]);}coutansendl;}return 0;
} 一种二维dp
这一块存疑
也是一种非常常见的dp式 f f f : d p i , j m i n k i { d p k , j − 1 w ( k , i ) } :dp_{i,j}min_{ki}\{dp_{k,j-1}w(k,i)\} :dpi,jminki{dpk,j−1w(k,i)}
按理说它跟上一块的区间dp是不同类型的但是仿佛只要 w w w满足引理1 F F F也有同样的结论。我没看到过严格证明OIWIKI上也没找到对应介绍但是大家好像都默认这是正确的而且我目前也没找到反例…并不是很懂
反正用定理2来优化该dp的话时间复杂度是 O ( n 2 ) O(n^2) O(n2)的
例题
HDU Division
#includebits/stdc.h
using namespace std;
#define ll int
const ll N10005;
ll t,n,m;
ll dp[N][5010];
ll mas[N];
ll f(ll l,ll r)
{return (mas[r]-mas[l])*(mas[r]-mas[l]);
}
ll d[N][5010];
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cint;for(int s1;st;s){cinnm;for(int i1;in;i) cinmas[i];sort(mas1,mas1n);memset(dp,0x3f,sizeof dp);dp[0][0]0;for(int j1;jm;j){d[n1][j]n;for(int in;i;--i){ll tmp0x3f3f3f3f;ll p;for(int kd[i][j-1];kd[i1][j];k){if(tmpdp[k][j-1]f(k1,i)){tmpdp[k][j-1]f(k1,i);pk;}}dp[i][j]tmp;d[i][j]p;}}coutCase s: dp[n][m]endl;}return 0;
} 一些满足四边形不等式的函数类
若 w 1 ( i , j ) , w 2 ( i , j ) w_{1(i,j)},w_{2(i,j)} w1(i,j),w2(i,j)均满足四边形不等式或区间包含不等式则 ∀ c 1 , c 2 ≥ 0 \forall c_1,c_2\geq 0 ∀c1,c2≥0, c 1 w 1 ( i , j ) c 2 w 2 ( i , j ) c_1w_{1(i,j)}c_2w_{2(i,j)} c1w1(i,j)c2w2(i,j)也对应地满足四边形不等式或区间包含不等式若存在函数 f , g f,g f,g使得 w l , r f r − g l w_{l,r}f_r-g_l wl,rfr−gl,则 w w w满足四边形恒等式等号永远成立。当 f , g f,g f,g单调增的时候 w w w还满足区间包含不等式设 h x h_x hx是一个单调增的下凸函数若 w w w满足四边形不等式以及区间包含不等式则 h ( w ( x ) ) h(w(x)) h(w(x))也满足四边形不等式以及区间包含不等式设 h x h_x hx是一个下凸函数,若 w w w满足四边形恒等式以及区间包含不等式则 h ( w ( x ) ) h(w(x)) h(w(x))满足四边形不等式
具体证明详见OIWIKI
这里以NOI 2009 诗人小G的dp递推式来试着用这些结论证一下决策单调性 d p i m i n 0 ≤ j i { d p j ∣ s i − s j − 1 − L ∣ P } dp_imin_{0\leq ji}\{dp_j|s_i-s_j-1-L|^P\} dpimin0≤ji{dpj∣si−sj−1−L∣P},其中 s i i ∑ k 1 i a k s_ii\sum_{k1}^{i}a_k sii∑k1iak, a k 0 a_k0 ak0为常值
这里 w j , i ∣ s i − s j − 1 − L ∣ P w_{j,i}|s_i-s_j-1-L|^P wj,i∣si−sj−1−L∣P,我们不妨记 m j , i s i − s j − 1 − L m_{j,i}s_i-s_j-1-L mj,isi−sj−1−L,则 w j , i ∣ m j , i ∣ P w_{j,i}|m_{j,i}|^P wj,i∣mj,i∣P
我们考虑利用第2条结论记 f i s i − 1 − L , g i s i f_is_i-1-L,g_is_i fisi−1−L,gisi,显然 m j , i f i − g j m_{j,i}f_i-g_j mj,ifi−gj,故 m j , i m_{j,i} mj,i满足四边形不等式,又 f i , g i f_i,g_i fi,gi显然单增故 m j , i m_{j,i} mj,i满足区间包含不等式
又函数 ∣ x ∣ P |x|^P ∣x∣P显然是一个下凸函数故由第4条结论可知 w j , i m j , i w_{j,i}m_{j,i} wj,imj,i也满足四边形不等式。再由定理1该dp式满足决策单调性。证毕。
可以看到如果式子能记住的话在面对一些比较复杂的递推式的时候能够较从容地推出决策单调性如果直接用四边形不等式的定义硬证这题的话还是需要不少分类讨论和强大的推柿子能力的啊…只会套公式的屑
与图形相结合
来自一位大佬的奇妙讨论,从另一个视角帮助我们理解了决策单调性
这里讨论一维最优化dp也就是 F F F : d p i m i n j ≤ i { d p j w ( j , i ) } :dp_imin_{j\leq i}\{dp_jw(j,i)\} :dpiminj≤i{dpjw(j,i)}
决策单调性意味着决策点是单调的换句话说每一个点能够作为最优决策点的范围是一段连续区间 在绿色区间内的点都是被 d p j 1 dp_{j_1} dpj1更新在黄色区间内的点都是被 d p j 2 dp_{j_2} dpj2更新不会出现黄色区间内有某个点是被 d p j 1 dp_{j_1} dpj1更新的情况否则就违背了决策单调性的定义
从几何视角来看这一事实。我们考虑 g j ( i ) g_j(i) gj(i)表示 d p j w ( j , i ) dp_jw(j,i) dpjw(j,i),则 d p i dp_i dpi可以重新表示为 d p i m i n j ≤ i { g j ( i ) } dp_imin_{j\leq i}\{g_j(i)\} dpiminj≤i{gj(i)}。我们可以将 g j ( i ) g_j(i) gj(i)看成 j j j为常值 i i i为自变量的一个函数那么 d p i dp_i dpi本质上就是在所有函数 g j ( i ) g_j(i) gj(i)里取最小值来转移
还是以上图为例绿色区间内的点对应函数 g j 1 ( i ) g_{j_1}(i) gj1(i),黄色区间内对应函数 g j 2 ( i ) g_{j_2}(i) gj2(i),我们可以得到一个结论两个函数只能有一个交点否则就会出现前一段是 g j 1 ( i ) g_{j_1}(i) gj1(i)更小,中间是 g j 2 ( i ) g_{j_2}(i) gj2(i),后面又变成 g j 1 ( i ) g_{j_1}(i) gj1(i)更小的局面那就违背了决策单调性的定义。反过来如果只有一个交点的话这两段区间就满足决策单调性
整体来看我们可以得到如果所有 g j ( i ) g_j(i) gj(i)两两之间都至多只有一个交点的话 F F F是满足决策单调性的。个人感觉该命题的逆命题并不成立毕竟实际在转移的时候只用考虑最小值的变化值较大的函数之间是如何纠缠的我们并不关系。所以该结论应该只适用于证明决策单调性而不能证否决策单调性
接下来我们考虑如果 g j ( i ) g_j(i) gj(i)之间至多只有一个交点需要满足什么性质
该大佬给出的两个条件是 g j ( i ) g_j(i) gj(i)之间可以通过平移相互变换 g j ( i ) g_j(i) gj(i)的导函数在定义域内单调增/减凸性唯一
以下分别是不满足对应条件的反例 这两个条件不一定充分只是感觉上可能也够了
然后大佬给出的一些总结 如果导函数递增求最大值或导函数递减求最小值 用单调栈 如果导函数递增求最小值或导函数递减求最大值 用单调队列
具体怎么用单调栈单调队列我会在后面有所涉及
决策单调性的常见优化手段
二分队列
这应该算是最常见的一种利用决策单调性来优化dp的手段了。它只能用于决策点单调增的情况。
考虑之前的一个结论每一个决策点的更新范围是一段连续区间。这意味着相邻两个决策点的更新范围之间存在着一个分界线 K K K,当 i k ik ik的时候由前一个点 j 1 j_1 j1更新之后就由后一个点 j 2 j_2 j2更新,并且 j 1 j_1 j1就再也没有机会了。那么我们就可以维护一个单调队列来实现每次 O ( l o g n ) O(logn) O(logn)的更新
具体来说我们的单调队列中的每一个元素是一个三元组 { P , l p , r p } \{P,l_p,r_p\} {P,lp,rp},分别表示当前的决策点 P P P,它能更新区间的左界 l p l_p lp,它能更新区间的右界 r p r_p rp。那么当我们尝试更新 d p i dp_i dpi的时候 弹出队头。因为队列里的点的对应决策区间是单调的所以我们可以直接将 r p i r_pi rpi的队头三元组不断弹出。 用队头的 P P P更新 d p i dp_i dpi 将三元组 { i , l i , r i } \{i,l_i,r_i\} {i,li,ri}放入队列尾部。那么怎么求 l i , r i l_i,r_i li,ri?在求 l i l_i li之前我们要意识到一个事实我们所求的 l p , r p l_p,r_p lp,rp都是建立在已经遍历到的点的信息上而建立的换句话说随着后面新的点 i i i加入它的决策区间有可能会完全包含某一个点 P P P的决策区间。这一点很好理解原本 l i , r i l_i,r_i li,ri就是由 i i i更新的但是因为我们还没有遍历到 i i i,所以这段区间就会先被其它点占据。所以我们在求 l i l_i li之前要先将队尾那些完全不会比 i i i优的点踢出。具体如何判断我们只要看一下在 l p l_p lp处 i i i是否比 P P P更优即可。如果是显然 P P P就再也没有机会比 i i i更优了因为 p i pi pi。 该操作之后 i i i就不能将队尾的 P P P的区间完全覆盖了我们就可以利用单调性二分一下两者的决策区间的边界作为 l i l_i li.至于 r i r_i ri,我们直接设成 n n n即可。毕竟此时后面的点还没加入我们只能用 i i i来更新它们。
贴个模板
//该模板适用于最小化问题若求最大化自行将对应不等号取反即可
//cal(j,i):g_j(i)ll que[N];//单调队列hd1,tl0;que[tl]0;ls[0]1,rs[0]n;for(int i1;in;i){while(hdtlrs[que[hd]]i) hd;//弹出无用点dp[i]cal(que[hd],i);pre[i]que[hd];while(hdtlcal(i,ls[que[tl]])cal(que[tl],ls[que[tl]])) tl--;//弹出无用点ll lls[que[tl]],rn1;while(lr){ll mid(lr)1;if(cal(i,mid)cal(que[tl],mid)) rmid-1;//二分查找i与que[tl]的转移分界点也就是最小的满足i优于que[tl]的点else lmid1;}p_ansr1;if(p_ansn) continue;//i并没有用rs[que[tl]]p_ans-1;que[tl]i;//插入队列ls[i]p_ans,rs[i]n;}Tips:二分决策区间边界的时候右界设置为n1,因为i有可能完全不如P优要防一手 如果 w ( j , i ) w(j,i) w(j,i)我们能够以 O ( 1 ) O(1) O(1)的复杂度求出的话该方法的时间复杂度式 O ( n l o g ) O(nlog) O(nlog)的
例题
NOI 2009 诗人小G
dp式并不难列出关于其决策单调性我们已经在上一块里证明过了所以这里直接用二分队列即可
数据范围有点大记得开long double
code
#includebits/stdc.h
using namespace std;
#define ll long long
#define ld long double
#define IL inline
#define endl \n
const ll N100010;
const ll mod998244353;
const ll inf1e18;
inline int read()
{int X0; bool flag1; char chgetchar();while(ch0||ch9) {if(ch-) flag0; chgetchar();}while(ch0ch9) {X(X1)(X3)ch-0; chgetchar();}if(flag) return X;return ~(X-1);
}
int n,L,P;
char s[N][50];
ld mas[N];
int ls[N],rs[N],pre[N];//记录最优决策点
int que[N];
int hd,tl,p_ans;
ld dp[N];
ld ksm(ld x,ll y)
{ld ans1;while(y){if(y1) ansans*x;xx*x;y1;}return ans;
}
ld cal(ll k,ll x)
{return dp[k]ksm(abs(mas[x]-mas[k]-1-L),P);
}
void solve()
{nread();Lread();Pread();for(int i1;in;i) scanf(%s,s[i]);// for(int i1;in;i) cins[i];for(int i1;in;i){mas[i]mas[i-1]strlen(s[i])1;}hd1,tl0;que[tl]0;ls[0]1,rs[0]n;for(int i1;in;i){while(hdtlrs[que[hd]]i) hd;dp[i]cal(que[hd],i);pre[i]que[hd];while(hdtlcal(i,ls[que[tl]])cal(que[tl],ls[que[tl]])) tl--;ll lls[que[tl]],rn1;while(lr){ll mid(lr)1;if(cal(i,mid)cal(que[tl],mid)) rmid-1;//二分查找i与que[tl]的转移分界点也就是最小的满足i优于que[tl]的点else lmid1;}p_ansr1;if(p_ansn) continue;//i并没有用rs[que[tl]]p_ans-1;que[tl]i;//插入队列ls[i]p_ans,rs[i]n;}///if(dp[n]inf){puts(Too hard to arrange);}else{printf(%lld\n,(ll)dp[n]);vectorstring ans;ll posn;while(1){ll xpre[pos]1;string ss;for(int ix;ipos;i) sss[i],ss ;sss[pos];ans.push_back(ss);pospre[pos];if(pos0) break;}reverse(ans.begin(),ans.end());for(auto i:ans) coutiendl;}puts(--------------------);
}
int main()
{// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll t;tread();while(t--)solve();return 0;
}二分栈
一般用于最优决策点是不增的情况。在原本的二分队列的做法中我们从队列的首部取出最优决策点从队列的尾部放入决策点。那么如果决策点是不增的意味着我们需要从队列的尾部取最优决策点。这样取和放的操作都是在队列的尾部我们只要用一个栈来实现就好了。同样的相邻的两个决策点更新的区间会有一个边界我们不妨记为 k l , r k_{l,r} kl,r,当尝试加入 i i i的时候记队列倒数第一个元素为 p 1 p_1 p1,倒数第二个元素为 p 2 p_2 p2,那么如果 k p 1 , p 2 ≤ k p 2 , i k_{p_1,p_2}\leq k_{p_2,i} kp1,p2≤kp2,i,那么 p 2 p_2 p2就可以踢掉了因为它不管在什么时候都不会是 i , p 1 , p 2 i,p_1,p_2 i,p1,p2中的最优解。然后将 i i i加入队列之后再按照 k p 1 , p 2 k_{p_1,p_2} kp1,p2是否 ≤ i \leq i ≤i来踢即可
JSOI2001 柠檬
思路
首先不难发现最优选择下每一段的首尾的颜色就是这段的 s 0 s_0 s0否则我们就可以将首尾的没用的点分出去自称一段贡献一定更优
所以我们可以按照不同的颜色来分开处理 d p i m a x c o l j c o l i , j ≤ i { d p j − 1 w ( j , i ) } dp_imax_{col_jcol_i,j\leq i}\{dp_{j-1}w(j,i)\} dpimaxcoljcoli,j≤i{dpj−1w(j,i)},其中 w ( j , i ) ( s u m i − s u m j 1 ) 2 w(j,i)(sum_i-sum_j1)^2 w(j,i)(sumi−sumj1)2
这里我们画图就能发现决策点是单调不增的按照上文与图形结合的方法所以可以使用二分栈。但是这题的决策单调性是在相同颜色的点之间才存在的所以我们要分开来做二分栈
然后每一个点不会从0转移所以一开始也不用把0放进去
code
#include bits/stdc.h
#define pii pairint,int
#define il inline
#define ll long long
using namespace std;
#define bc(idx) vt[idx].size()-1
#define bd(idx) vt[idx].size()-2
#define g(a,b) vt[a][b]
const int N200000;
const ll inf1e18;
ll n;
ll mas[N];
vectorll vt[N];
ll dp[N];
ll ls[N],rs[N];
mapll,ll mp;
ll sum[N];
ll gt(ll k,ll num)
{return dp[k-1]mas[k]*num*num;
}
ll gtf(ll a,ll b)
{ll l1,rn;while(lr){ll midlr1;if(gt(a,mid-sum[a]1)gt(b,mid-sum[b]1)) rmid-1;else lmid1;}return r1;
}
void solve()
{cinn;for(int i1;in;i){cinmas[i];mp[mas[i]];sum[i]mp[mas[i]];}for(int i1;in;i){ll idxmas[i];while(vt[idx].size()2 gtf(g(idx,bd(idx)),g(idx,bc(idx)))gtf(g(idx,bc(idx)),i)) vt[idx].pop_back();vt[idx].push_back(i);while(vt[idx].size()2 gtf(g(idx,bd(idx)),g(idx,bc(idx)))sum[i]) vt[idx].pop_back();dp[i]gt(g(idx,bc(idx)),sum[i]-sum[g(idx,bc(idx))]1);}coutdp[n]endl;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();return 0;
}分治
分治的方法主要用于同一层之间的点相互之间线性无关的情况。
比如 F 1 F_1 F1 : d p i , j m i n { d p i − 1 , k w ( k , i ) } :dp_{i,j}min\{dp_{i-1,k}w(k,i)\} :dpi,jmin{dpi−1,kw(k,i)}. F 2 F_2 F2 : d p i m i n { a k w ( k , i ) } :dp_imin\{a_kw(k,i)\} :dpimin{akw(k,i)}
可以看到同一层之间的点不会相互转移
那么如果同一层的点满足决策单调性的话也就是意味着决策点是单调的我们就可以采用分治的策略来优化转移的过程
假设当前需要转移的区间是 [ L , R ] [L,R] [L,R],决策点的选择区间是 [ p l , p r ] [p_l,p_r] [pl,pr](显然一开始转移区间和决策点的选择区间都为 [ 1 , n ] [1,n] [1,n])设 m i d L R 2 mid\frac{LR}{2} mid2LR,我们可以先暴力求出 m i d mid mid的最优决策点 p o s pos pos,那么 [ L , m i d − 1 ] [L,mid-1] [L,mid−1]的决策点选择区间就是 [ p l , p o s ] [p_l,pos] [pl,pos], [ m i d 1 , R ] [mid1,R] [mid1,R]的决策点选择区间就是 [ p o s , p r ] [pos,p_r] [pos,pr]那么这样分治下去就好了。
如果我们可以 O ( 1 ) O(1) O(1)求代价的话对 m i d mid mid求 p o s pos pos的时间复杂度就只有 O ( n ) O(n) O(n),再加上每次要处理的区间长度会变成原本的一半所以处理区间为n的复杂度是 f ( n ) O ( n ) O ( f ( n / 2 ) ) f(n)O(n)O(f(n/2)) f(n)O(n)O(f(n/2)),总复杂度是 O ( n l o g n ) O(nlogn) O(nlogn)
一个板子
void Solve(ll l,ll r,ll pl,ll pr)
{//当前分治处理区间是[l,r],最佳决策区间是[pl,pr]ll midlr1;ll pos;//mid的最佳决策点dp[mid]gt(pospl,mid);for(int ipl1;imin(mid-1,pr);i){if(gt(i,mid)dp[mid]) dp[mid]gt(posi,mid);}if(lmid) Solve(l,mid-1,pl,pos);if(rmid) Solve(mid1,r,pos,pr);
}JSOI2016 灯塔
大意
给定 h i h_i hi对于每一个 i i i,要求 ∀ j , p i ≥ h j − h i ∣ i − j ∣ \forall j,p_i\geq h_j-h_i\sqrt{|i-j|} ∀j,pi≥hj−hi∣i−j∣ ,求最小的 p i p_i pi
思路
不妨先将绝对值去掉那么 p i { m i n { h j i − j − h i } j i m i n { h j j − i − h i } j i p_i\left\{\begin{matrix} min\{h_j\sqrt{i-j}-h_i\} ji\\ min\{h_j\sqrt{j-i}-h_i\} ji \end{matrix}\right. pi{min{hji−j −hi}min{hjj−i −hi}jiji
那么我们只要处理第一个式子就好了第二个式子只要把整个数组反一下即可
可以发现 p i m i n { h j i − j − h i } p_imin\{h_j\sqrt{i-j}-h_i\} pimin{hji−j −hi}满足决策单调性并且 p i p_i pi之间相互无关所以直接分治就解决了
code
#includebits/stdc.h
using namespace std;
#define ll long long
#define IL inline
#define endl \n
const ll N5e510;
double ep1e-9;
const ll mod998244353;
const ll inf1e18;
ll n;
ll mas[N];
double dp1[N],dp2[N];
double gt(ll p,ll x)
{return mas[p]sqrt(x-p)-mas[x];
}
void Solve(ll l,ll r,ll pl,ll pr,double *dp)
{// if(lr||plpr) return;ll mid(lr)1;ll pospl;for(int ipl;imin(mid,pr);i){if(gt(i,mid)-dp[mid]-ep) dp[mid]gt(posi,mid);//要取0}if(lmid) Solve(l,mid-1,pl,pos,dp);if(rmid) Solve(mid1,r,pos,pr,dp);
}
void solve()
{cinn;for(int i1;in;i) cinmas[i];Solve(1,n,1,n,dp1);reverse(mas1,mas1n);Solve(1,n,1,n,dp2);for(int i1;in;i){double xfmax(dp1[i],dp2[n-i1]);cout(ll)ceil(x)endl;}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// ll t;tread();while(t--)solve();return 0;
}SDOI2016 征途
CF321 E
类莫队做法
注意到分治要保证时间复杂度的前提是每次求 w w w代价的复杂度是 O ( 1 ) O(1) O(1)的
但是有一类 w w w比较特殊关于区间的信息的记录比如区间数字种类数等。这种问题我们一般可以离线下来用莫队处理那么仿照莫队用左右端点的连续移动就可以做到 O ( 1 ) O(1) O(1)转移了因为我们的决策点的选择范围也刚好是一个连续的区间所以这样的话复杂度是正确的
CF868 F
CmdOI2019 任务分配问题
#includebits/stdc.h
#include iostream
using namespace std;
#define ll int
#define IL inline
#define endl \n
const ll N3e410;
double ep1e-9;
const ll mod998244353;
const ll inf1e9;
struct Tree
{ll tr[N];#define low(x) x(-x)void add(ll x,ll y){while(xN){tr[x]y;xlow(x);}}ll sum(ll x){ll ans0;while(x){anstr[x];x-low(x);}return ans;}
}T;
ll n,k;
ll mas[N];
ll dp[N],pp[N];
namespace Mo
{int L1,R0;ll ans0;int col[N];ll cnt[N];void add1(ll pos,ll op)//区间左边{if(op1){ansT.sum(n1)-T.sum(col[pos]);T.add(col[pos],1);}else{ans-T.sum(n1)-T.sum(col[pos]);T.add(col[pos],-1);}}void add2(ll pos,ll op)//区间右边{if(op1){ansT.sum(col[pos]-1);T.add(col[pos],1);}else{ans-T.sum(col[pos]-1);T.add(col[pos],-1);}}ll gt(ll l,ll r){l;while(Ll) add1(L,0);while(Ll) add1(--L,1);while(Rr) add2(R--,0);while(Rr) add2(R,1);return pp[l-1]ans;}
}
void Solve(ll l,ll r,ll pl,ll pr)
{ll mid(lr)1;ll pos;dp[mid]Mo::gt(pospl,mid);for(int ipl1;imin(mid-1,pr);i){if(dp[mid]Mo::gt(i,mid)) dp[mid]Mo::gt(posi,mid);}if(lmid) Solve(l,mid-1,pl,pos);if(rmid) Solve(mid1,r,pos,pr);
}
void solve()
{cinnk;for(int i1;in;i){cinMo::col[i];}for(int i1;in;i) pp[i]Mo::gt(0,i);for(int i1;ik;i){Solve(1,n,0,n);for(int j1;jn;j) pp[j]dp[j];}coutpp[n]endl;}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// ll t;tread();while(t--)solve();return 0;
}SMAWK
SMAWK的用途跟分治一样用于处理同一层之间没有转移关系的情况但是复杂度会更优可以达到 O ( n ) O(n) O(n)
我们考虑从另一个角度来理解决策单调性 定义1 若矩阵A满足∀i,j∈[0,k],pos(i)pos(j)则称A为单调矩阵。若A的任意子矩阵均为单调矩阵则称A为完全单调矩阵 重新定义四边形不等式 定义2 对于n*m的矩阵A若 ∀ 1 i 1 i 2 ≤ n , 1 ≤ j 1 , ≤ j 2 ≤ m \forall 1i_1i_2\leq n,1\leq j_1,\leq j_2\leq m ∀1i1i2≤n,1≤j1,≤j2≤m,均有 A i 1 , j 1 A i 2 , j 2 ≤ A i 1 , j 2 A i 2 , j 1 A_{i_1,j_1}A_{i_2,j_2}\leq A_{i_1,j_2}A_{i_2,j_1} Ai1,j1Ai2,j2≤Ai1,j2Ai2,j1,则称A满足四边形不等式 快速判断矩阵是否满足四边形不等式 定理1 对于n*m的矩阵A若 ∀ 1 i n , 1 ≤ j m \forall 1in,1\leq jm ∀1in,1≤jm,均有 A i , j A i 1 , j 1 ≤ A i , j 1 A i 1 , j A_{i,j}A_{i1,j1}\leq A_{i,j1}A_{i1,j} Ai,jAi1,j1≤Ai,j1Ai1,j,则称A满足四边形不等式 定理2 若矩阵A满足四边形不等式则A以及 A T A^{T} AT是完全单调矩阵 证明就不给了感兴趣可以去看看原论文
接下来考虑 d p i m i n j i { a j w ( j , i ) } dp_imin_{ji}\{a_jw(j,i)\} dpiminji{ajw(j,i)},放到矩阵上当 j i ji ji时 A i , j d p j w ( j , i ) , j ≥ i A_{i,j}dp_jw(j,i),j\geq i Ai,jdpjw(j,i),j≥i时令 A i , j i n f A_{i,j}inf Ai,jinf那么求 d p i dp_i dpi其实就是在第i行找最小值对应的列j.如果矩阵是一个单调矩阵也就是dp满足决策单调性我们就可以采用SMAWK
SMAWK的核心内容是reduce的过程当列数m远大于n的时候我们的枚举量会多很多但是其实一行只会对应一个最优列所以大量列是多余的reduce过程就是在去除这些冗余列
当然为了保证一行只有一个答案我们要限定取每一行最左边/最右边的最小值**这一点在与WQS二分结合的时候很重要**
其步骤如下 1初始定义 k 1 2当 n ≥ m 时结束过程否则比较 A k , k A_{k,k} Ak,k 和 A k , k 1 A_{k,k1} Ak,k1 3若 A k , k ≥ A k , k 1 A_{k,k}\geq A_{k,k1} Ak,k≥Ak,k1删除第 k 列k ← max(k − 1*,* 1)回到步骤 2 4若 A k , k A k , k 1 A_{k,k} A_{k,k1} Ak,kAk,k1 且 k n删除第 n 1 列回到步骤 2 5若 A k , k A k , k 1 A_{k,k} A_{k,k1} Ak,kAk,k1 且 k nk ← k 1回到步骤 2。
每一步的原因还是很显然的这里不多赘述了。复杂度是 O ( m n ) O(mn) O(mn)
为了保证线性复杂度的正确性可以用链表实现
struct Node
{ll val,opt;Node *lst,*nxt;Node(){valopt0;lstnxtNULL;}
};
struct List
{ll len;//列表长度Node *s,*e;List(){len0;snew Node();s-opt1;enew Node();e-opt-1;s-nxte;e-lsts;}void append(ll x){//将x加入尾部Node *nnew Node();n-valx;Node *ae-lst;//尾部元素a-nxtn;n-lsta;n-nxte;e-lstn;len;//长度}List(const List a){//Copylen0;snew Node();s-opt1;enew Node();e-opt-1;s-nxte;e-lsts;Node *na.s-nxt;while(n-opt!-1){append(n-val);nn-nxt;}}Node* del(Node *n){--len;Node *an-lst,*bn-nxt;a-nxtb,b-lsta;delete(n);return a;//前一个节点}
};
struct submat
{List r,c;//row,column
}A;
submat Reduce(const submat A)
{submat B;B.r(List)A.r;B.c(List)A.c;int nA.r.len;//行数int mA.c.len;//列数Node *nrB.r.s-nxt;//第一个节点Node *ncB.c.s-nxt;ll k1;while(nm){if(get(nr-val,nc-val)get(nr-val,nc-nxt-val)){ncB.c.del(nc);m--;if(k1){--k;nrnr-lst;}else{//k1nrB.r.s-nxt;ncB.c.s-nxt;}}else if(kn){B.c.del(nc-nxt);m--;}else{k;nrnr-nxt;ncnc-nxt;}}return B;
}reduce之后我们就真正开始SMAWK了
SMAWK(A) 表示计算 n × m 的完全单调矩阵 A 的每行最小值所在
列。步骤如下
1若 min(n, m) 1 直接计算答案2对Areduce得到矩阵B,并且我们取其所有偶数行组成一个新矩阵C4递归SMAWK©,得到C的每一行的最小值所在位置4对于B中的奇数行其答案在相邻两行的答案之间那么之间暴力遍历一下即可。该步骤的复杂度为 O ( m ) O(m) O(m)
void SMAWK(submat A)
{int nA.r.len;//行数int mA.c.len;//列数if(n1){ll xA.r.s-nxt-val;//只有一行Node *ncA.c.s-nxt;ll maxn0;ll maxp0;//最值位置while(nc-opt!-1){if(get(x,nc-val)maxn){maxpnc-val,maxnget(x,nc-val);}ncnc-nxt;}ans[x]maxp;//存储最大值所在位置///return;}if(m1){ll yA.c.s-nxt-val;Node *nrA.r.s-nxt;//第一行while(nr-opt!-1){ans[nr-val]y;nrnr-nxt;}return;}submat BReduce(A);submat C;C.cList(B.c);//首先保存每一列的信息Node *nrB.r.s-nxt;//行第一个元素bool fl0;while(nr-opt!-1){if(fl) C.r.append(nr-val);//C保存偶数行nrnr-nxt;fl^1;}//得到一个只有偶数行列不变的矩阵SMAWK(C);//递归nrB.r.s-nxt;fl0;Node *ncB.c.s-nxt;//列指针while(nr-opt!-1){if(!fl){ll zans[nr-nxt-val];//已经处理过了这里是有值的ll xnr-val;ll maxn0,maxp0;if(z0) zinf;while(nc-opt!-1 nc-valz){//枚举列//返回的是最右边的最小值if(get(x,nc-val)maxn){maxnget(x,nc-val);maxpnc-val;}ncnc-nxt;}if(nc-lst-valz) ncnc-lst;ans[x]maxp;}nrnr-nxt;fl^1;}
}理论上是可以平替分治的但是写起来太烦了。。。
有一份短一点的代码
//求每行最左边最小值
int pre[N],suf[N],M[N],n,m,ans1e18,P0;
vectorintL,H;
mapint,intMp[N];
ll get(ll a,ll b)
{//返回第a行第b列的元素
}
int pre[N],suf[N],M[N],P0;
void del(int x)
{if (pre[x]!-1)suf[pre[x]]suf[x]; else Psuf[x];pre[suf[x]]pre[x];
}
vectorint reduce(vectorintX,vectorintY)
{for (int i0;iY.size();i) pre[i]i-1,suf[i]i1;int x0,y0;P0;for (int nmslY.size()-X.size();nmsl0;nmsl--){if (get(X[x],Y[y])get(X[x],Y[suf[y]])){ysuf[y];del(pre[y]);if (x) ypre[y],x--;} else{if (xX.size()-1) del(suf[y]);else{ysuf[y];x;}}}vectorintret;for (int iP;i!Y.size();isuf[i]) ret.push_back(Y[i]);return ret;
}
void Solve(vectorintX,vectorintY)
{Yreduce(X,Y);if (X.size()1){M[X[0]]Y[0];return;}vectorintZ;for (int i0;iX.size();i)if (!(i%2)) Z.push_back(X[i]);Solve(Z,Y);for (int i0;iX.size();i){if (!(i%2)) continue;int llower_bound(Y.begin(),Y.end(),M[X[i-1]])-Y.begin();int r0;if (iX.size()-1) rY.size()-1;else{rlower_bound(Y.begin(),Y.end(),M[X[i1]])-Y.begin();}M[X[i]]Y[l];while (lr){l;if (get(X[i],Y[l])get(X[i],M[X[i]])) M[X[i]]Y[l];}}
}
signed main()
{cinnm;for (int i1;in;i){H.push_back(i);}for (int i1;im;i) L.push_back(i);Solve(H,L);
}WQS二分
可以与其它方法结合在一起达到一个非常优秀的时间复杂度
关于WQS二分本身的内容这里就不多赘述了可以去看其它文章理解一下这里主要讲一下如何将其应用在决策单调性中
考虑一类问题将一个序列强制分为k段每一段 [ l , r ] [l,r] [l,r]有一个价值 w ( l , r ) w(l,r) w(l,r),问总价值最小的分段
假设将序列分为k段的最优价值为 f k f_k fk如果所有的 ( k , f k ) (k,f_k) (k,fk)组成一个凸函数那么我们就可以使用WQS二分了。外层枚举斜率内层就去掉了分段的限制就可以使用二分队列/斜率优化/分治等措施了。
现在问题还是很多的比如凸性的证明WQS二分的边界问题内部求最优值时更新的取等问题等。一个一个来
WQS多解情况
多解情况是指答案K与多个点在一条线段上此时我们无法直接通过枚举斜率来做到只切到点K所以我们需要在枚举的同时让得到的方案具有完全的偏序来保证我们枚举斜率的时候知道当前斜率对应的答案是哪一点的答案是线段左端点的还是右端点的从而保证后面二分调整mid的时候不会弄混淆。很重要的一点是我们需要的只是正确的斜率不需要保证当前斜率做出来的最优点一定是K,因为 f k m i d ∗ k b f_kmid*kb fkmid∗kb,其中斜率 m i d mid mid和截距 b b b都是二分之后确定的值在同一线段上的点做出的 m i d , b mid,b mid,b都是一样的。
那么为了做到严格偏序我们需要对每一个属性都定义大小
这篇博客讲的很清晰我可能讲的有点抽象可以去再看看 满足四边形不等式的序列划分问题的答案凸性以及WQS二分的方案构造
这里我们尝试证明满足四边形不等式的序列划分问题都具有凸性 不妨先来看另一个问题给定一张n个点的DAG点 i i i与点 j j j当 i j ij ij时有权值 w ( i , j ) w(i,j) w(i,j),问从1走到n的经过k条边的最短路 简单转化一下这个问题的dp方程就是我们熟悉的: d p i , j m i n { d p k , j − 1 w ( k , i ) } dp_{i,j}min\{dp_{k,j-1}w(k,i)\} dpi,jmin{dpk,j−1w(k,i)}, d p i , j dp_{i,j} dpi,j表示走到i经过j条边的最短路
设 f k f_k fk表示经过k条边的最短路
下面我们尝试证明当权值矩阵w满足四边形不等式的时候 f k f_k fk是一个下凸函数。换句话说 ∀ k ∈ [ 2 , n − 2 ] \forall k\in[2,n-2] ∀k∈[2,n−2] f k 1 − f k f k − f k − 1 f_{k1}-f_kf_k-f_{k-1} fk1−fkfk−fk−1 引理∀1 ≤ s r t ≤ n − 1*,* f(s) f(t) ≥ f(r) f(s t − r) 如果我们能够证明该引理的话带入 s k − 1 , r k , t k 1 sk-1,rk,tk1 sk−1,rk,tk1,则命题得证
下面尝试证明引理 不妨记 f s f_s fs对应的最优方案是 p 1 , p 2 . . . p s 1 p_1,p_2...p_{s1} p1,p2...ps1, f t f_t ft对应的最优方案是 q 1 , q 2 , . . q t 1 q_1,q_2,..q_{t1} q1,q2,..qt1
记 v r − s 0 vr-s0 vr−s0,如果我们能够找到 i ∈ [ 1 , s ] i \in [1,s] i∈[1,s],满足 p i ≤ q i v q i v 1 ≤ p i 1 ( i v 1 ≤ s v 1 ≤ t ) p_i\leq q_{iv}q_{iv1}\leq p_{i1}(iv1\leq sv1\leq t) pi≤qivqiv1≤pi1(iv1≤sv1≤t),就能够构造路径 R 1 : R_1: R1: p 1 , . . . p i , q i v 1 , q i v 2 , . . q t 1 p_1,...p_i,q_{iv1},q_{iv2},..q_{t1} p1,...pi,qiv1,qiv2,..qt1,以及路径 R 2 : R_2: R2: q 1 , . . . q i v , p i 1 , p i 2 , . . . p s 1 q_1,...q_{iv},p_{i1},p_{i2},...p_{s1} q1,...qiv,pi1,pi2,...ps1(也就是把两段路径的后半段交换了一下并且保证一定交换了一部分)
两段路径的长度分别是 i − 1 ( t 1 − i − v − 1 ) 1 t − v t − r s i-1(t1-i-v-1)1t-vt-rs i−1(t1−i−v−1)1t−vt−rs,以及 i − 1 v ( s 1 − i − 1 ) 1 s v r i-1v(s1-i-1)1svr i−1v(s1−i−1)1svr,
那么由f的定义, R 1 R_1 R1的路径长度 l e n R 1 ) ≥ f t − r s lenR_1) \geq f_{t-rs} lenR1)≥ft−rs, R 2 R_2 R2的路径长度 l e n ( R 2 ) ≥ f r len(R_2)\geq f_{r} len(R2)≥fr,
由四边形不等式 w ( p i , q i v 1 ) w ( q i v , p i 1 ) ≤ w ( q i v q i v 1 ) w ( p i , p i 1 ) w(p_i,q_{iv1})w(q_{iv},p_{i1})\leq w(q_{iv}q_{iv1})w(p_i,p_{i1}) w(pi,qiv1)w(qiv,pi1)≤w(qivqiv1)w(pi,pi1)
故 f s f t ≥ l e n ( R 1 ) l e n ( R 2 ) ≥ f t − r s f r f_sf_t\geq len(R_1)len(R_2)\geq f_{t-rs}f_r fsft≥len(R1)len(R2)≥ft−rsfr
第一个不等式是因为 R 1 , R 2 R_1,R_2 R1,R2与原本路径的区别只有中间衔接的一段
由上我们只要证明存在这样的一个 i i i即可。 不妨记路径P将 ( 1 , n ] (1,n] (1,n]分成了s个部分其中第i个部分是 ( p i , p i 1 ] (p_i,p_{i1}] (pi,pi1]
我们记 a i a_i ai表示 q i v q_{iv} qiv在哪一段那么如果存在 i i i, a i a i 1 k a_ia_i1k aiai1k,我们就找到答案为k了。
记 b i a i − i b_ia_i-i biai−i,显然 b 1 ≥ 0 , b s 1 ≤ − 1 b_1\geq 0,b_{s1}\leq -1 b1≥0,bs1≤−1后者是因为 a s 1 − ( s 1 ) ≤ s − ( s 1 ) − 1 a_{s1}-(s1)\leq s-(s1)-1 as1−(s1)≤s−(s1)−1,此外显然 b i − b i − 1 0 b_i-b_{i-1}0 bi−bi−10或 − 1 -1 −1,故 b i − b i − 1 ≥ − 1 b_i-b_{i-1}\geq -1 bi−bi−1≥−1
由此序列b中一定存在一个-1,取最靠前的-1记为 b i 1 b_{i1} bi1.它前面一定是 b i 0 b_i0 bi0,故 a i a i 1 a_ia_{i1} aiai1
这样我们就找到了一个合法的 i i i,引理得证故命题得证 Q.E.D 这段证明还是非常玄妙(玄幻)的。当然它对于我们的方案构造也有帮助
WQS二分中有时候会存在要求为k但是 k l , k r kl,kr kl,kr且 l , r , k l,r,k l,r,k在一条线段上的情况这时候我们一般通过限定边数尽可能多/少来保证取到线段的端点。但是想要构造方案的话就会不知所措了
我们记答案斜率为mid,这条包含答案k的线段的端点为 ( l , f l ) , ( r , f r ) (l,f_l),(r,f_r) (l,fl),(r,fr),则 ∀ i ∈ [ l , r ] , f i f l m i d ∗ ( i − l ) \forall i\in[l,r],f_if_lmid*(i-l) ∀i∈[l,r],fiflmid∗(i−l)
我们可以先把 l , r l,r l,r对应的最优方案找出来长度分别为 l , r l,r l,r,那么按照上述证明中的构造方式我们得到长度为 k , l r − k k,lr-k k,lr−k的路径 R 1 , R 2 R_1,R_2 R1,R2,记其路径长度分别为 l e n ( R 1 ) a , l e n ( R 2 ) b len(R_1)a,len(R_2)b len(R1)a,len(R2)b,有 a ≥ f l m i d ∗ ( k − l ) , b ≥ f l m i d ∗ ( l r − k − l ) a\geq f_lmid*(k-l),b\geq f_lmid*(lr-k-l) a≥flmid∗(k−l),b≥flmid∗(lr−k−l)
且有 2 f l m i d ∗ ( k − l ) m i d ∗ ( l r − k − l ) 2 f l m i d ∗ ( r − l ) ≤ a b ≤ f l f r 2 f l m i d ∗ ( r − l ) 2f_lmid*(k-l)mid*(lr-k-l)2f_lmid*(r-l)\leq ab\leq f_lf_r2f_lmid*(r-l) 2flmid∗(k−l)mid∗(lr−k−l)2flmid∗(r−l)≤ab≤flfr2flmid∗(r−l)
第二个不等号的原因见证明片段
发现 a b ab ab被边界夹住了故 a f l m i d ∗ ( k − l ) a f_lmid*(k-l) aflmid∗(k−l),由此a就是 f k f_{k} fk,我们就得到了长度为k的构造方案
以上内容参考 《The d-Edge Shortest-Path Problem for a Monge Grapll》以及APIO2021《决策单调性与四边形不等式》 WQS外层二分时的边界
一般来说直接取 [ − i n f , i n f ] [-inf,inf] [−inf,inf]即可或者稍微算一下卡住边界
不管是这样的 还是这样的 只要边界范围足够就不会有问题。但是有一类分段问题图像长这样 分段为0的时候总价值为0然后开始分段之后价值随分段减少。不考虑0的话后面的一段也是满足凸函数的那么这个对我们的边界会有影响吗个人感觉没有因为我们只要保证wqs二分之后在做最优决策的时候保证不让段数为0即可
比如这题就是这个情况CF321 E (在分治部分此题作为练习出现当然它也可以WQS二分毕竟它满足四边形不等式而我们已经证明了该类问题的凸性)
那么到这里理论部分就差不多完善了我们就可以看看应用了
不妨就看看这题CF321 E
按照套路我们外层枚举斜率内层就是每一段的贡献要减去一个 m i d mid mid,问最优分段数及其对应的总贡献。dp式满足决策单调性可以直接上单调队列复杂度是 O ( n l o g n 2 ) O(nlogn^2) O(nlogn2),外层 O ( l o g ) O(log) O(log),内层 O ( n l o g ) O(nlog) O(nlog)可以看到比普通的 O ( n 2 l o g ) O(n^2log) O(n2log)分治要优化了不少
code
#include bits/stdc.h
#define pii pairint,int
#define il inline
#define ll long long
using namespace std;
const int N4010;
const ll inf1e18;
ll n,m;
ll mp[N][N];
ll cnt[N];
ll sum[N][N];
ll dp[N];
ll que[N];
ll ls[N],rs[N];
ll ANS;
ll cal(ll l,ll r)
{//l1-rreturn sum[r][r]-sum[l][r]-sum[r][l]sum[l][l];
}
ll gt(ll k,ll x,ll val)
{return dp[k]cal(k,x)-val;
}
bool judge(ll x)
{ll hd1,tl0;que[tl]0;ls[0]1,rs[0]n;for(int i1;in;i){cnt[i]0,ls[i]rs[i]0;while(hdtlrs[que[hd]]i) hd;dp[i]gt(que[hd],i,x);cnt[i]cnt[que[hd]]1;while(hdtlgt(i,ls[que[tl]],x)gt(que[tl],ls[que[tl]],x)) tl--;ll Lls[que[tl]],Rn1;while(LR){ll mid(LR)1;if(gt(i,mid,x)gt(que[tl],mid,x)) Rmid-1;else Lmid1;}// couti que[tl] R1 gt(i,R1,x) gt()ll p_ansR1;if(p_ansn) continue;rs[que[tl]]p_ans-1;que[tl]i;ls[i]p_ans,rs[i]n;}ANSdp[n];
// coutx cnt[n] ANS ANSm*xendl;return cnt[n]m;//尽可能分多段尽可能选靠后的点转移
}
void solve()
{cinnm;for(int i1;in;i){for(int j1;jn;j){cinmp[i][j];if(ij) mp[i][j]0;}}for(int i1;in;i){for(int j1;jn;j){sum[i][j]sum[i][j-1]sum[i-1][j]mp[i][j]-sum[i-1][j-1];}}ll l-1e18,r0;while(lr){ll mid(lr)1;if(judge(mid)) rmid-1;else lmid1;}judge(r1);coutANSm*(r1)endl;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();return 0;
}
IOI2000 邮局 加强版
SDOI2016 征途
套路都差不多套一个WQS的事内层看情况用不同的优化手段
Akvizna
你面临 n 名参赛者的挑战最终要将他们全部战胜。 每一轮中都会淘汰一些选手你会得到这一轮奖金池中 被淘汰者 除以 这一轮对手总数 比例的奖金。
例如某一轮有 10 个对手淘汰了 3 个那么你将获得奖金池中 3/10 的奖金。
假设每一轮的奖金池均为一元Mirko 希望通过恰好 k 轮赢得比赛那么他最多可能获得多少奖金呢
你只需要输出答案保留 9 位小数即可。
这题略阴间二分的时候不枚举小数的话过不了肥肠卡精度不过思维难度一般
#include bits/stdc.h
using namespace std;
#define ll long long
#define double long double
#define endl \n
const double eps1e-12;
const ll inf1e18;
const ll N 1e510;
int n,m;
double dp[N];
double ANS;
double inv[N];
ll cnt[N];//分的段数
ll que[N];
ll ls[N],rs[N];
double gt(ll k,ll x)
{return dp[k](double)((x-k)*1.0*inv[n-k]);
}
bool judge(double x)
{ll hd1,tl0;que[tl]0;ls[0]1,rs[0]n;for(int i1;in;i){cnt[i]0,ls[i]rs[i]0;while(hdtlrs[que[hd]]i) hd;cnt[i]cnt[que[hd]]1;dp[i]gt(que[hd],i)-x;// couti que[hd] dp[i]endl;while(hdtlgt(i,ls[que[tl]])gt(que[tl],ls[que[tl]])) tl--;ll Lls[que[tl]],Rn1;while(LR){ll mid(LR)1;if(gt(i,mid)gt(que[tl],mid)) Rmid-1;else Lmid1;}ll p_ansR1;if(p_ansn) continue;rs[que[tl]]p_ans-1;que[tl]i;ls[i]p_ans,rs[i]n;}ANSdp[n];// coutx cnt[n] ANS ANSm*xendl;return cnt[n]m;
}
void solve()
{cinnm;for(int i1;in;i) inv[i]1.0/(i*1.0);// for(int i1;in;i)// {// for(int j1;jmin(i,m);j)// {// for(int kj-1;ki;k)// {// dp[i][j]max(dp[i][j],dp[k][j-1](double)((i-k)*1.0/(n-k)));// }// }// }// judge(0);// for(double i-2;i2;i0.1) judge(i);double l-100,r100;while(lepsr){double mid(lr)/2.0;if(judge(mid)) rmid;else lmid;}judge(r);// coutr1endl;coutfixedsetprecision(9)ANSm*1.0*(r)endl;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();return 0;
}
Tips
做WQS二分一定要注意问题函数是一个上凸包还是下凸包
注意左右边界
有时候也是也是要二分小数的
斜率优化
基本的斜率优化本人已经在另一篇博客中讲的很详细了从入门到精通应该都有了。
然后更多的应用大概就是与WQS二分结合了吧
注意点好像也没啥毕竟WQS二分之后内部就是一个纯纯的一维dp
SDOI2016 征途
Akvizna
值得一提的还有这道题JSOI2001 柠檬
之前在二分栈里提过它但其实它也可以用斜率优化做但是因为斜率实际上是递减的所以内部维护凸包的时候是用一个栈因为最优点在最后了放入点也是在最后这个还是比较少见的
code
#includebits/stdc.h
using namespace std;
#define ll long long
#define ld long double
#define IL inline
#define endl \n
const ll N100010;
const ll mod998244353;
const ll inf1e18;
inline int read()
{int X0; bool flag1; char chgetchar();while(ch0||ch9) {if(ch-) flag0; chgetchar();}while(ch0ch9) {X(X1)(X3)ch-0; chgetchar();}if(flag) return X;return ~(X-1);
}
ll n,a;
ll dp[N];
vectorll col[N],st[N];//栈
ll gt(ll x,ll c)
{return dp[col[c][x]-1]c*x*x-2*x*c;
}
double Slope(ll a,ll b,ll col)
{if(ab) return inf;double xgt(a,col)-gt(b,col);xx*1.0;double ya-b;y*1.0;return x/y;
}
void solve()
{cinn;for(int i1;i10000;i) col[i].push_back(0);for(int i1;in;i){cina;ll lencol[a].size();col[a].push_back(i);//放入idif(len1) st[a].push_back(1);//st存的是横坐标颜色前缀和else{//维护上凸包while(st[a].size()1Slope(st[a][st[a].size()-2],st[a][st[a].size()-1],a)2*a*len) st[a].pop_back();//sum_ilenll idst[a][st[a].size()-1];dp[i]dp[col[a][id]-1]a*(1len-id)*(1len-id);while(st[a].size()1Slope(st[a][st[a].size()-2],st[a][st[a].size()-1],a)Slope(st[a][st[a].size()-1],len,a)) st[a].pop_back();st[a].push_back(len);}dp[i]max(dp[i],dp[i-1]a);}coutdp[n]endl;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// ll t;tread();while(t--)solve();return 0;
}一些特殊情况
可以看到如果题目已经有了决策单调性大部分情况下还是比较套路的但是有些时候问题在全局上不满足决策单调性并不意味着局部也没有。
还是JSOI2001 柠檬这道题它就是在同种颜色内部满足决策单调性这么一看这真是道好题啊哪哪都这么与众不同
以及2016NAIP H
大意
有n个物品每个物品有一个体积 w i w_i wi和价值 v i v_i vi现在要求对 V ∈ [ 1 , m ] V∈[1,m] V∈[1,m]求出体积为 V V V的 背包能够装下的最大价值 1 ≤ n ≤ 1000000 ; 1 ≤ m ≤ 100000 ; 1 ≤ w i ≤ 300 ; 1 ≤ v i ≤ 1 0 9 1≤n≤1000000;1≤m≤100000;1≤w_i≤300;1≤v_i≤10^9 1≤n≤1000000;1≤m≤100000;1≤wi≤300;1≤vi≤109
其实就是对每一个 V V V做一个多重背包
思路
发现每一个物品的体积都比较小所以可以按照体积分类。那么对于同一种体积的物品我们肯定贪心选择价值最大的所以可以排个序
考虑 d p i , j dp_{i,j} dpi,j表示使用体积 ≤ i \leq i ≤i的物品总体积为j的最大价值。我们可以将所有需要更新的体积按照%i来重新编号。比如当前i是2m是9我们就可以将 0 , 2 , 4 , 6 , 8 0,2,4,6,8 0,2,4,6,8化为一类各自重新编号为 0 , 1 , 2 , 3 , 4 0,1,2,3,4 0,1,2,3,4 1 , 3 , 5 , 7 , 9 1,3,5,7,9 1,3,5,7,9划为一类编号同理
这样的好处就是我们对于每一个ij的范围也只有 [ 0 , i ] [0,i] [0,i]这么大了以及同一组体积内部的差恰好为i那么物品就可以直接按照价值大小贪心塞了。
那么此时dp的意义就变了。如果当前是在更新%ia的体积则 d p i , j dp_{i,j} dpi,j表示使用体积 ≤ i \leq i ≤i的物品总体积为 j ∗ i a j*ia j∗ia的最大值
%ia时 d p i , j m a x k ≤ j { d p i − 1 , k w ( k , j ) } dp_{i,j}max_{k\leq j}\{dp_{i-1,k}w(k,j)\} dpi,jmaxk≤j{dpi−1,kw(k,j)},其中 w ( k , j ) w(k,j) w(k,j)表示体积i的物品中最大的 j − k j-k j−k个物品的价值和记为前缀和 v t i , j − k vt_{i,j-k} vti,j−k
简单证一下四边形不等式:
考虑 i , i 1 , j , j 1 , i 1 j i,i1,j,j1,i1j i,i1,j,j1,i1j w ( i , j ) w ( i 1 , j 1 ) 2 v t j − i w(i,j)w(i1,j1)2vt_{j-i} w(i,j)w(i1,j1)2vtj−i w ( i 1 , j ) w ( i , j 1 ) v t j − i − 1 v t j − i 1 2 v t j − i a j − i 1 − a j − i − 1 ≤ w ( i , j ) w ( i 1 , j 1 ) w(i1,j)w(i,j1)vt_{j-i-1}vt_{j-i1}2vt_{j-i}a_{j-i1}-a_{j-i-1}\leq w(i,j)w(i1,j1) w(i1,j)w(i,j1)vtj−i−1vtj−i12vtj−iaj−i1−aj−i−1≤w(i,j)w(i1,j1)
得证
那么直接分治即可
code
#include bits/stdc.h
using namespace std;
#define ll long long
#define double long double
#define endl \n
const double eps1e-11;
const ll inf1e18;
const ll N 1e610;
ll n,m;
vectorll vt[310];
ll dp[N],pp[N];
ll gt(ll id,ll x,ll mod,ll res)
{return pp[id*modres]vt[mod][x-id-1];
}
bool cmp(ll a,ll b)
{return ab;
}
void Solve(ll l,ll r,ll pl,ll pr,ll mod,ll res)
{if(lr) return;ll mid(lr)1;ll posmid;dp[mid*modres]pp[mid*modres];for(int imin(mid-1,pr);ipl;--i){if(mid-i(int)vt[mod].size()) break;if(gt(i,mid,mod,res)dp[mid*modres]) dp[mid*modres]gt(posi,mid,mod,res);}Solve(l,mid-1,pl,pos,mod,res);Solve(mid1,r,pos,pr,mod,res);
}
void solve()
{cinnm;for(int i1;in;i){ll a,b;cinab;vt[a].push_back(b);}for(int i1;i300;i){sort(vt[i].begin(),vt[i].end(),cmp);for(int j1;j(int)vt[i].size();j) vt[i][j]vt[i][j-1];}for(int i1;i300;i){if(!vt[i].size()) continue;//枚举物品体积的类别for(int j0;ji;j){//枚举%ij的体积Solve(0,(m-j)/i,0,(m-j)/i,i,j);}for(int j1;jm;j) dp[j]max(dp[j],dp[j-1]);for(int j1;jm;j) pp[j]max(dp[j],dp[j-1]);}for(int i1;im;i) coutpp[i] ;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();return 0;
}
本来想用SMAWK写的但是一直MLE不懂求懂的佬教教
当然这题的决策单调性也是分组才有的很抽象感觉本人是不可能看出来的哭
总结
大工程希望对自己大家有用
参考文章
OIWIKI
Bein, W W, Larmore, L L, and Park, J K. The d-edge shortest-path problem for a Monge graph. United States: N. p., 1992. Web.
Bein, W W, Brucker, P, and Park, J K. Applications of an algebraic Monge property. United States: N. p., 1993. Web.
DP的决策单调性优化总结
Divide and Conquer DP
决策单调性 - MCAdam
关于决策单调性与图像的结合
彭思进 《决策单调性与四边形不等式》
