dp的一些优化

单调队列优化

　　当dp[i][j]从一段区间转移而来，且这段区间随i,j的后移而后移/前推时，可以考虑用单调队列扫一遍，可将O(n^2)优化至O(n)。

四边形不等式优化

　　形如dp[i][j]=min{dp[i][k]+dp[k+1][j]+cost[i][j]}的dp方程，//取max不一定满足四边形不等式

　　若对于i<=i'<=j<=j',有w(i',j)<=w(i,j')(即区间包含单调性)和w(i,j)+w(i',j')<=w(i',j)+w(i,j')(即四边形不等式),则：

　　　　1.dp(i,j)+dp(i',j')<=dp(i',j)+dp(i,j')；
　　　　2.记g(i,j)为对dp(i,j)最优的k,则决策点g(i,j)满足单调性,即g(i,j)<=g(i+1,j)<=g(i+1,j+1) => g(i-1,j)<=g(i,j)<=g(i,j+1)/g(i,j-1)<=g(i,j)<=g(i+1,j)；

　　因此枚举k时不必从1到i，可以直接由g(i-1,j)到g(i,j+1);对于固定的i-j，i,j=>g(i-1,j)~g(i,j+1)、i+1,j+1=>g(i,j+1)~g(i+1,j+2)、i+2,j+2=>g(i+1,j+2)~g(i+2,j+3)…这些区间互不重叠，因此Σg(i,j+1)-g(i-1,j)<=n

　　时间复杂度由O(n^3)优化到O(n^2)。

　　一般而言，为了保证循环到dp(i,j)时g(i,j-1),g(i+1,j)已知，i应倒序枚举，j应正序枚举。至于内外层自变量，依题目要求保证顺利转移即可。

决策单调性优化

　　决策单调性指的是，dp[i]的最优转移点k随i

　　二维情况可用四边形不等式证明。

　　两种实现方法：

　　1）分治

　　　　代码难度较小，但得出dp值无先后顺序（从中间开始二分，也就从中间开始算），一般适用于二维dp（dp[i][j]由dp[i-1][j]转移而来，而i相同时同一维彼此线性无关）O(nlogn)

 1 //l,r: 被决策点的下/上界
 2 //L,R: 决策点的下/上界 
 3 void work(int i,int l,int r,int L,int R)
 4 {
 5     if(l>r)
 6         return;
 7     
 8 //    mid: [l,r]中二分被决策点
 9 //    pos: mid的决策点 
10     int pos=-1,mid=(l+r)>>1;
11     for(int j=L;j<=min(mid-1,R);j++)
12     {
13         int val=dp[i-1][j]+w(j,mid);
14         if(val<dp[i][mid])
15             dp[i][mid]=val,pos=j;
16     }
17 // mid值已算出，从二分序列剔除
18     work(i,l,mid-1,L,pos);
19     work(i,mid+1,r,pos,R);

　　2）单调栈/单调队列

　　　　较为普适，但必须能在较短时间内（通过预处理）算出w(i,j)，比如说O(1)。总复杂度O(nlogn)。

 //sta[][0]记录栈中元素，sta[][1]记录此元素作为决策点的最小被决策点
 //找到以p作为决策点的最小被决策点（与栈顶的决策点相比即可）
int find(int p){
    int ll=p+1,//或ll=pos[top]，因为在work()中已弹出会被覆盖的决策点
        rr=m+1,mid;
    while(ll<rr){
        mid=(ll+rr)>>1;
        if(f[sta[r][0]]+b[sta[r][0]+1].y*b[mid].x>f[p]+b[p+1].y*b[mid].x)
            rr=mid;
        else ll=mid+1;
    }
    return ll;
}
void work(){
    l=0;r=0;
    for(i=1;i<=m;i++){
        if(l<r&&sta[l+1][1]<=i) l++;  //写while更稳妥
        f[i]=f[sta[l][0]]+w(sta[l][0],i);
        // i的决策区间能完全覆盖栈顶决策点的决策区间
        while(l<r&&f[sta[r][0]]+w(sta[r][0],sta[r][1])>=f[i]+w(i,sta[r][1])) r--;
        int pos=find(i);
        if(pos<=m){
            sta[++r][0]=i;
            sta[r][1]=pos;
        }
    }
}

// 模板根据不同题目会有较大变动

　　P5504 [JSOI2011] 柠檬

比较罕见的决策点单调递减的题，而且不是全序列单调性，只有大小相同的贝壳之间转移才有单调性，所以二分找最优决策点时mid代表的不是序列编号，而是在同种大小贝壳中的编号。写的时候犯了不少错误，比如x写成y,忘记mid特殊性等。

　　在将i压入栈前，要先检查当前栈顶p代替i成为最优决策点的时间是否大于(栈顶-1)q代替栈顶成为最优的时间；若是，则要不断将栈顶弹出。否则会存在时间t，q比p优，但p不比i优，此时存在q比i优的可能性，但由于先前没有把p弹出，此时无法绕过p直接比较i和q，从而错过最优决策点。这个思想很重要，大部分决策单调的题都要考虑类似情况。

斜率优化

　　未完

凸优化

　　未完