DP训练——斜率优化DP

2020-02-27 本文已影响0人云中翻月

斜率优化DP

斜率优化DP涉及到的模型较多，在编写习题题解前，先做出如下规律总结。

如何识别斜率优化DP

按照正常思路列出DP方程后，如发现其形如 $f[i]=max(f[j]+v(j)*w(i))$ 的形式，即可使用斜率优化DP。（ $v(j)$ 和 $w(i)$ 分别表示两个关于j和i的函数）

斜率优化DP的化简步骤

1 忽略方程中的 $min$ 或 $max$ 符号。
2 假设外层循环为 $i$ 时，对于决策点 $j$ 和 $k(j<k)$ ，若需要保证 $j$ 的决策比 $k$ 的决策更优，则 $f[j]+v(j)*w(i)<f[k]+v(k)*w(i)$ 。
3 对上式分离参数，将 $j，k$ 有关项作为分式（这个分式就是斜率）放在左侧， $i$ 有关项放在右侧，并保持 $j$ 和 $k$ 的相对顺序不变。得 $\frac { f[j]-f[k]}{ v(j)-v(k)} < w(i)$ （该不等式中间的符号（小于号或大于号）取决于 $v(j)$ 和 $v(k)$ 的相对大小）
4 上式可以抽象为一个点集 $(v(j),f[j])$ ，于是可以通过如下代码计算斜率。

int X(int i){
    return v(i);
}
int Y(int i){
    return f[i];
}
double d(int i,int j){
    return ((double)Y(i)-Y(j))/(X(i)-X(j));
}

5 根据如下规则可判断凸包的形状。
如果如上不等式的符号为大于号，则为下凸包（斜率递增）
如果不等式的符号为小于号，则为上凸包（斜率递减）
6 根据如下规则可判断维护斜率的方式。
下凸包对应目标斜率 $w(i)$ 递增，上凸包对应目标斜率 $w(i)$ 递减，满足这两个条件之一时就可以使用双端队列维护凸包。
下凸包对应目标斜率 $w(i)$ 递减，上凸包对应目标斜率 $w(i)$ 递增，满足这两个条件之一时就可以使用双端队列维护凸包。
如果目标斜率 $w(i)$ 没有单调性，就需要在凸包中二分。
如果如果 $v(j)$ 和 $v(k)$ 的相对大小无法确定，就需要用平衡树维护凸包，或者整体二分。

斜率优化DP的其他注意事项

1 对于二维状态的斜率优化DP（或者存在转移点限制的斜率优化DP，例如BZOJ4709），需要在内层循环中维护多个单调队列。
2 因为计算斜率时存在分式计算，所以需要考虑是否存在分母为零的情况，如若存在，则需要特判。（例如在BZOJ3675中，就将其斜率直接设为了 $INF$ ，即永远不会被算入答案）

斜率优化DP习题

BZOJ1597
题意
$n(n<=50000)$ 个矩形，给定每个矩形的长宽（长宽不可交换）。每次可以选出若干个矩形，代价是矩形中长宽的最值乘积。求选出所有矩形的最小代价。
题解
首先通过排序（按矩形的长升序排序，相同则按宽升序排序），去除完全包含于其他矩形的矩形。
这样剩下的矩形中任意选出一段 $[j,i]$ ，则长度的最大值为 $land[i].x$ ，宽度的最大值为 $land[j].y$ 。
然后进行dp。
状态定义： $f[i]$ 表示处理好前 $i$ 个矩形，需要的最小代价。
边界： $f[0]=0$
目标： $f[n]$
转移方程： $f[i]=min(f[i],f[j]+land[i].x*land[j+1].y),1<=j<=i-1$
这样的时间复杂度为 $O(n^2)$ ，考虑优化。
忽略 $min$ ，将该式展开，并让内层循环变量 $j$ 对应的状态位于方程左边，得到 $f[j]=-land[i].x*land[j+1].y+f[i]$ 。
队首需要维护的条件：
当外层循环为 $i$ 时，对于决策点 $j$ 和 $k(j<k)$ ，若需要保证 $j$ 的决策比 $k$ 的决策更优，则 $f[j]+land[i].x*land[j+1].y<f[k]+land[i].x*land[k+1].y$
分离参数（分离原则为将 $j$ 和 $k$ 有关的项作为分式放在左边，并保持j和k的相对位置不变）得 $\frac{f[j]-f[k]}{land[j+1].y-land[k+1].y}<-land[i].x$ （注意这里计算时， $land[j+1].y-land[k+1].y$ 为负数，不等号方向会改变）
因此，为了保证队首存储着最优决策，需要保证队首相邻两点斜率 $<-land[i].x$ 。
队尾需要维护的条件：
对应的dp数组可理解为处于第一象限的点集 $(land[x].y,f[x])$ 。（因为排序的原因，这里的横坐标单调减，故队首为横坐标最大的点）
最终关系式为小于号，就需要维护一个上凸包，即保证凸包上相邻两点斜率单调递减。
根据本文开始的规则，题目满足上凸包中， $-land[i].x$ 递减，所以用单调队列维护。

上凸包
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=50000+5;
const ll INF=0x3f3f3f3f3f3f3f3fll;
int n;
ll f[maxn];
struct node{
    ll l,r;
    bool operator<(const node& h)const{return l<h.l||(l==h.l&&r<h.r);}
}square[maxn],land[maxn];
double d(int x,int y){ //计算x到y的直线斜率，x在y的左侧
    return ((double)f[y]-f[x])/(land[y+1].r-land[x+1].r);
}
void pre(){
    sort(square+1,square+n+1);
    int cnt=0;
    square[n+1].l=-INF,square[n+1].r=-INF;
    for(int i=1;i<=n;i++){
//        if(square[i].l<=square[i+1].l&&square[i].r<=square[i+1].r) continue;
        while(cnt&&square[i].r>=land[cnt].r) cnt--; //用这种方式去除完全包含于其他矩形的矩形
        land[++cnt].l=square[i].l,land[cnt].r=square[i].r;
    }
    n=cnt;
    /*
    D(cnt);E;
    for(int i=1;i<=n;i++){
        D(land[i].l);D(land[i].r);E;
    }
    */
}
int q[maxn];
int head=1,tail=0;
void dp(){
    f[0]=0;
    q[++tail]=0;
    for(int i=1;i<=n;i++){
        while(head<tail&&d(q[head],q[head+1])>(double)(-land[i].l)) head++;
        f[i]=f[q[head]]+land[i].l*land[q[head]+1].r;
        while(head<tail&&d(q[tail-1],q[tail])<=d(q[tail],i)) tail--;
        q[++tail]=i;
    }
    printf("%lld",f[n]);
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("BZOJ1597.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld%lld",&square[i].l,&square[i].r);
    pre();
    dp();
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

BZOJ4518
题意
给定长度为 $n(n<=3000)$ 的序列，需要将其分为 $m(m<=3000)$ 段，使得这 $m$ 段长度的方差 $v$ 最小，求最小方差 $v*m^2$ 。（可以证明， $v*m^2$ 是一个整数）
题解
首先推导方差的公式。（设 $a_i$ 表示第i段的长度）
$v*m^2=\frac {\sum_{i=1}^{m}(a_i-\bar{a})^2}{m}*m^2$
因为 $\bar{a} =\frac { \sum_{i=1}^{m}a_i}{m}$ 得
$v*m^2=\sum_{i=1}^{m}(m*a_{i}^{2}-2*a_i*\sum_{i=1}^{m}a_i+\frac{(\sum_{i=1}^{m}a_i)^{2}}{m})$
将求和符号展开后，得到
$v*m^2=m*\sum_{i=1}^{m}(a_{i}^{2})-(\sum_{i=1}^{m}a_i)^2$
其中 $(\sum_{i=1}^{m}a_i)^2$ 为定值，因此只需要考虑 $\sum_{i=1}^{m}(a_{i}^{2})$ 的最小值。
状态定义： $f[i,j]$ 表示前 $i$ 个数字分为 $j$ 段的最小 $\sum_{k=1}^{j}(a_{k}^{2})$
目标： $m*f[n,m]-(\sum_{i=1}^{m}a_i)^2$
边界： $f[0,0]=0$ ，其他为 $INF$
转移方程： $f[i,j]=min(f[k,j-1]+(a_{k+1}+...+a_{i})^{2})$
预处理前缀和 $s_i=a_1+...+a_i$ 后，可在 $O(1)$ 时间内计算 $(a_{k+1}+...+a_{i})^{2}$ 。
故总时间复杂度为 $O(n^2*m)$ 。
考虑优化时间复杂度，即对于状态 $i，j$ ，要高效找到前继的最优状态 $k，j-1$ 。
队首需要维护的条件：
当外层循环为 $i，j$ 时，对于决策点 $k$ 和 $l(k<l)$ ，若需要保证 $k$ 的决策比 $l$ 的决策更优，则 $f[k,j-1]+(s_i-s_{k})^{2}<f[l,j-1]+(s_i-s_{l})^{2}$
分离参数（将 $k，l$ 有关项作为分式（这个分式就是斜率）放在左侧， $i$ 有关项放在右侧）得 $\frac { (f[k,j-1]+s_{k}^{2})-(f[l,j-1]+s_{l}^{2})}{s_k-s_l}>2*s_i$ （注意 $s_k-s_l<0$ ，故推导时不等号符号会改变）
因此，为了保证队首存储着最优决策，需要保证队首相邻两点斜率 $>2*s_i$
队尾需要维护的条件：
对应的dp数组可理解为处于第一象限的点集 $(s_x,f[x,y]+s_{x}^{2})$ 。
最终关系式为大于号，就需要维护一个下凸包，即保证凸包上相邻两点斜率单调递增。
根据本文开始的规则，题目满足下凸包中， $2*s_i$ 递增，所以用单调队列维护。

下凸包
PS：代码中的状态定义和题解中的状态定义，第一维和第二维的含义交换了。
题解链接 https://www.luogu.com.cn/problemnew/solution/P4072
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=3000+5;
const int INF=0x3f3f3f3f;
int n,m,s[maxn];
int f[maxn][maxn]; //f[i,j]表示处理到第i天，已经走了前j段的最小平方和
int head,tail,q[maxn];
double d(int i,int x,int y){
    return ((double)f[i][x]-f[i][y]+s[x]*s[x]-s[y]*s[y])/(s[x]-s[y]);
}
void init(){
    head=1,tail=0;
}
void dp(){
    init();
    memset(f,INF,sizeof(f));
    for(int i=0;i<=n;i++) f[1][i]=s[i]*s[i];
    for(int i=2;i<=m;i++){
        init();
        q[++tail]=0;
        for(int j=1;j<=n;j++){
            while(head<tail&&d(i-1,q[head],q[head+1])<2*s[j]) head++;
            f[i][j]=f[i-1][q[head]]+(s[j]-s[q[head]])*(s[j]-s[q[head]]);
//            D(i);D(j);D(q[head]);D(f[i-1][q[head]]);D(f[i][j]);E;
            while(head<tail&&d(i-1,q[tail-1],q[tail])>d(i-1,q[tail],j)) tail--;
            q[++tail]=j;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
//  freopen("BZOJ4518.in","r",stdin);
    cin>>n>>m;
    int x;
    for(int i=1;i<=n;i++){
        cin>>x;
        s[i]=s[i-1]+x;
    }
    dp();
    cout<<(ll)m*f[m][n]-s[n]*s[n];
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

BZOJ3675
题意
长度为 $n(n<=100000)$ 的非负整数序列，可以切割 $k(k<=200)$ 次，每次得分为切割出的新的两个序列的元素和乘积，求最大得分。
题解
首先，注意到该题的得分与切割顺序无关。
证明：
考虑将一块 $abc$ 分为 $a,b,c$ 三块。
方法一：先分成 $a,bc$ 。答案为 $a(b+c)+bc=ab+ac+bc$ 。
方法二：先分成 $ab,c$ 。答案为 $c(a+b)+ab=ab+ac+bc$ 。
即最终得分仅与切割点有关。
状态定义： $f[i,j]$ 表示前 $i$ 个数字，切割 $j$ 次的最大得分
目标： $f[n,k]$
边界： $f[0,0]=0$
转移方程： $f[i,j]=max(f[k,j-1]+s_k*(s_i-s_k))$ ( $s[]$ 为序列的前缀和)
目前时间复杂度 $O(n^2*k)$ ，空间复杂度 $O(n*k)$ ，都需要优化。
优化空间复杂度可使用滚动数组（因为 $f[,j]$ 状态仅仅依赖于 $f[,j-1]$ 状态，所以可以滚动数组优化第二维），
考虑优化时间复杂度，即对于状态 $i，j$ ，要高效找到前继的最优状态 $k，j-1$ 。
队首需要维护的条件：
当外层循环为 $i，j$ 时，对于决策点 $k$ 和 $l(k<l)$ ，若需要保证 $k$ 的决策比 $l$ 的决策更优，则 $f[k,j-1]+s_k*(s_i-s_k)>f[l,j-1]+s_l*(s_i-s_l)$
分离参数（将 $k，l$ 有关项作为分式（这个分式就是斜率）放在左侧， $i$ 有关项放在右侧）得 $\frac{(f[k,j-1]-s_{k}^{2})-(f[l,j-1]-s_{l}^{2})}{s_k-s_l}<-s_i$
因此，为了保证队首存储着最优决策，需要保证队首相邻两点斜率 $<-s_i$ （注意这里 $s_k$ 可能等于 $s_l$ 所以需要特判）
队尾需要维护的条件：
对应的dp数组可理解为点集 $(s_x,f[x,y]-s_{x}^{2})$ 。
最终关系式为小于号，就需要维护一个上凸包，即保证凸包上相邻两点斜率单调递减。
根据本文开始的规则，题目满足上凸包中， $-s_i$ 递减，所以用单调队列维护。

上凸包
PS：根据状态定义，每次由

f[,j-1]

向

f[,j]

递推，所以外层循环变量

j

，内层循环变量

i

。
题解链接 https://www.luogu.com.cn/problemnew/solution/P3648
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e5+5;
const int maxk=200+5;
const double INF=1e18;
int n,k;
ll s[maxn];
ll f[maxn][2];
int head,tail,q[maxn];
double d(int i,int x,int y){
    if(s[x]==s[y]) return INF;
    return ((double)f[x][i&1]-s[x]*s[x]-(f[y][i&1]-s[y]*s[y]))/(s[x]-s[y]);
}
void init(){
    head=1,tail=0;
}
void dp(){
    init();
    for(int j=1;j<=k;j++){
        init();
        q[++tail]=0;
        for(int i=1;i<=n;i++){
            while(head<tail&&d(j-1,q[head],q[head+1])>-s[i]) head++;
            f[i][j&1]=f[q[head]][j-1&1]+s[q[head]]*(s[i]-s[q[head]]);
            while(head<tail&&d(j-1,q[tail-1],q[tail])<d(j-1,q[tail],i)) tail--;
            q[++tail]=i;
        }
    }
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("BZOJ3675.in","r",stdin);
    scanf("%d%d",&n,&k);
    ll x;
    for(int i=1;i<=n;i++){
        scanf("%lld",&x);
        s[i]=s[i-1]+x;
    }
    dp();
    cout<<f[n][k&1];
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

BZOJ4709
题意
长度为 $n$ 的正整数序列 $s[]$ ，每次可以从序列的一端选择一个区间，并选择一个常数 $s_0$ 。则该区间的贡献为区间内 $s_0$ 的个数 $t^2*s_0$ ，求总贡献的最大值。
题解
存在一个据说很显然的结论：每次选取的区间左右端点值必然相同，并且该值即为即将为区间选定的常数 $s_0$ 。
这个结论的证明不难，因为确定左端点的情况下，右端点的左右移动，都不会使得该区间的答案更优。
预处理出 $c[i]$ 表示 $s[i]$ 是相同大小的数中的第几个后，即可开始dp。
状态定义： $f[i]$ 表示前 $i$ 个数的最大贡献
目标： $f[n]$
边界： $f[0]=0$
转移方程： $f[i]=max(f[j-1]+s[i]*(c[i]-c[j]+1)^2),s[i]==s[j]$
当前时间复杂度为 $O(n^2)$ ，考虑优化，即对于状态 $j$ ，要高效找到前继的最优状态 $k$ 。
队首需要维护的条件：
当外层循环为 $i$ 时，对于决策点 $j$ 和 $k(j<k)$ ，若需要保证 $j$ 的决策比 $k$ 的决策更优，则 $f[j-1]+s[i]*(c[i]-c[j]+1)^2>f[k-1]+s[i]*(c[i]-c[k]+1)^2$
分离参数（将 $j，k$ 有关项作为分式（这个分式就是斜率）放在左侧， $i$ 有关项放在右侧）得 $\frac {(f[j-1]+s[j]*c[j]*c[j]-2*s[j]*c[j])-(f[k-1]+s[k]*c[k]*c[k]-2*s[k]*c[k])}{c[j]-c[k]}<2*s_i*c_i$ （化简时须利用 $s[i]=s[j]=s[k]$ ，并考虑 $c[j]<c[k]$ ）
因此，为了保证队首存储着最优决策，需要保证队首相邻两点斜率< $2s_ic_i$
队尾需要维护的条件：
对应的dp数组可理解为点集 $(c[x],f[x-1]+s[x]*c[x]*c[x]-2*c[x]*s[x])$ 。
最终关系式为小于号，就需要维护一个上凸包，即保证凸包上相邻两点斜率单调递减。
根据本文开始的规则，题目满足上凸包中， $2*s_i*c_i$ 递增，所以用单调栈维护。
（同时还需将上述分析中的队首条件改换为队尾条件，并且转换不等号方向（这是因为原先推导队首条件时，假设 $j<k$ 且 $j$ 比 $k$ 更优，而到了单调栈中，应假设 $j>k$ 且 $j$ 比 $k$ 更优））

上凸包
PS：
因为所有转移均在

s_i=s_j

这样的数字之间发生，所以实现中需要对每组相同的

s_i

维护一个单调栈。
另外，因为是单调栈不是单调队列，所以最优解会在尾端取到。因此dp时对应的四条语句有了顺序变化。
1 准备放入

i

，把不满足条件的栈顶弹出。
2

i

进栈。
3 更新目标斜率，把不满足目标斜率的栈顶弹出。
4 根据栈顶求

f[i]

。
题解链接 https://www.luogu.com.cn/problemnew/solution/P5504
代码如下

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100000+5;
const int maxs=10000+5;
const int INF=0x3f3f3f3f;
int n;
ll s[maxn],c[maxn];
int tot[maxs];
ll f[maxn];
vector<int>st[maxs];
ll X(int i){
    return c[i];
}
ll Y(int i){
    return f[i-1]+s[i]*c[i]*c[i]-2*c[i]*s[i];
}
ll calc(int i,int j){
    return f[j-1]+s[i]*(c[i]-c[j]+1)*(c[i]-c[j]+1);
}
double d(int i,int j){
    return ((double)Y(i)-Y(j))/(X(i)-X(j));
}
#define t1 st[t][st[t].size()-1]
#define t2 st[t][st[t].size()-2]
void dp(){
    for(int i=1;i<=n;i++){
        int t=s[i];
        while(st[t].size()>=2&&d(i,t1)>=d(t1,t2)) st[t].pop_back();
        st[t].push_back(i);
        while(st[t].size()>=2&&d(t1,t2)<=2*c[i]*s[i]) st[t].pop_back();
        f[i]=calc(i,t1);
    }
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("BZOJ4709.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&s[i]);
        tot[s[i]]++;
        c[i]=tot[s[i]];
    }
    dp();
    printf("%lld",f[n]);
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif