「动态规划」例题之状态和转移方程的优化

0x50「动态规划」例题

倍增优化DP

有些题目中，为了加速阶段的递推，我们会使用倍增去优化DP过程。
通常情况下，倍增优化DP会分为两步
第一步预处理出若干与2的整数次幂有关的状态
第二步将预处理出的状态拼凑出最终状态

例题

5701 开车旅行
首先利用set在 $O(nlogn)$ 内预处理出ga[i]和gb[i]，ga[i]表示i+1...n中dist(i,ga[i])次小的城市编号，gb[i]表示i+1~n中dist(i,gb[i])最小的城市编号。
考虑将天数作为“阶段”使用倍增优化DP
状态表示：
F[i,j,0]表示从j出发，行驶 $2^{i}$ 天，小A先开车，最终到达的城市
F[i,j,1]表示从j出发，行驶 $2^{i}$ 天，小B先开车，最终到达的城市
da[i,j,0]表示从j出发，行驶 $2^{i}$ 天，小A先开车，最终小A行驶的距离
da[i,j,1]表示从j出发，行驶 $2^{i}$ 天，小B先开车，最终小A行驶的距离
db[i,j,0]表示从j出发，行驶 $2^{i}$ 天，小A先开车，最终小B行驶的距离
db[i,j,1]表示从j出发，行驶 $2^{i}$ 天，小B先开车，最终小B行驶的距离
转移方程：
i=1时，因为此时 $2^{0}=1$ 是奇数，所以开车的人会产生轮换
$F[1,j,k]=F[0,F[0,j,k],1-k]$
$da[1,j,k]=da[0,F[0,j,k],1-k]+da[0,j,k]$
$db[1,j,k]=db[0,F[0,j,k],1-k]+db[0,j,k]$
i>1时，此时2的幂次方全是偶数，开车的人不变
$F[i,j,k]=F[i-1,F[i-1,j,k],k]$
$da[i,j,k]=da[i-1,F[i-1,j,k],k]+da[i-1,j,k]$
$db[i,j,k]=db[i-1,F[i-1,j,k],k]+db[i-1,j,k]$
边界：
$F[0,j,0]=ga[j],F[0,j,1]=gb[j]$
$da[0,j,0]=dist(j,ga[j]),da[0,j,1]=0$
$da[0,j,1]=0,da[0,j,1]=dist(j,gb[j])$
其中 $1\leq j \leq n$
目标：准备拼凑答案状态
1 倒序枚举所有2的整数次幂，并初始化两人的距离分别为A=0,B=0
2 若两人到达第 $2^{i}$ 天行驶路程未超过X（此时位于s城市），即 $A+B+da[i,s,0]+db[i,s,0]\leq X$ ，则令 $A+=da[i,s,0],B+=db[i,s,0],p=F[i,s,0]$ （注意讨论i=0的情况）
3 最终的A和B即为所求
时间复杂度： $O(nlogn)$
代码如下

/*
CH的第一个样例是错的
应该是
4 
2 3 1 4 
3 
4 
1 3 
2 3 
3 3 
4 3 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#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 maxm=1e4+5;
const int INF=0x3f3f3f3f;
int n,h[maxn],X0,m,s,x,ga[maxn],gb[maxn],tot,tag,f[40][maxn][2],t,da[40][maxn][2],db[40][maxn][2],ans;
ll ansA=1,ansB=0,A,B;
int temp[10];
set<pii>Set;
set<pii>::iterator it,it2;
int dis(int x,int y) {
    return abs(h[x]-h[y]);
}
bool cmp(int x,int y) {
    return dis(x,tag)<dis(y,tag)||(dis(x,tag)==dis(y,tag)&&h[x]<h[y]);
}
void Insert() {
    if(tag==1) int ha=1;
    it=Set.lower_bound(make_pair(h[tag],tag));
    it2=it,tot=0;
    if(it!=Set.begin()) it--,temp[++tot]=it->second;
    if(it!=Set.begin()) it--,temp[++tot]=it->second;
    it=it2;
    if(it!=Set.end()) temp[++tot]=it->second,it++;
    if(it!=Set.end()) temp[++tot]=it->second,it++;
    sort(temp+1,temp+tot+1,cmp);
    if(tot>=1) gb[tag]=temp[1];//小B沿着最近的走 
    if(tot>=2) ga[tag]=temp[2];
    Set.insert(make_pair(h[tag],tag));
}
void dp1() {
    for(int i=1; i<=n; i++){
        if(ga[i])f[0][i][0]=ga[i];
        if(gb[i])f[0][i][1]=gb[i];
    }
    for(int i=1; i<=n; i++) {
        for(int j=0; j<=1; j++) {
            if(f[0][i][j]) f[1][i][j]=f[0][f[0][i][j]][1-j];
        }
    }
    for(int i=2; i<=t; i++) {
        for(int j=1; j<=n; j++) {
            for(int k=0; k<=1; k++) {
                if(f[i-1][j][k]) f[i][j][k]=f[i-1][f[i-1][j][k]][k];
            }
        }
    }
}
void dp2() {
    for(int i=1; i<=n; i++) {
        if(ga[i]) {
            da[0][i][0]=dis(i,ga[i]),da[0][i][1]=0;
        }
        if(gb[i]) {
            db[0][i][0]=0,db[0][i][1]=dis(i,gb[i]);
        }
    }
    for(int i=1; i<=t; i++) {
        for(int j=1; j<=n; j++) {
            for(int k=0; k<=1; k++) {
                if(i==1) {
                    if(f[i][j][k]) da[i][j][k]=da[i-1][f[i-1][j][k]][1-k]+da[i-1][j][k];
                    if(f[i][j][k]) db[i][j][k]=db[i-1][f[i-1][j][k]][1-k]+db[i-1][j][k];
                } else {
                    if(f[i][j][k]) da[i][j][k]=da[i-1][f[i-1][j][k]][k]+da[i-1][j][k];
                    if(f[i][j][k]) db[i][j][k]=db[i-1][f[i-1][j][k]][k]+db[i-1][j][k];
                }
            }
        }
    }
}
void cal(int s,int x) {
    A=B=0;
    int k=0;
    for(int i=t; i>=0; i--) {
        if(A+B+da[i][s][k]+db[i][s][k]<=x&&f[i][s][k]) {
            A+=da[i][s][k],B+=db[i][s][k];
            if(i==0) k=1-k;
            s=f[i][s][k];
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("开车旅行.in","r",stdin);
    cin>>n;
    t=(log(n)/log(2))+1;
    for(int i=1; i<=n; i++) cin>>h[i];
    for(int i=n; i>=1; i--) tag=i,Insert();
//  for(int i=1; i<=n; i++) D(ga[i]),D(gb[i]),E;
    dp1();
    dp2();
    /*
    for(int i=0; i<=t; i++){
        for(int j=1;j<=n;j++)
            D(da[i][j][0]);
        E;
    }
    */
    cin>>X0>>m;
    for(int i=1; i<=n; i++) {
        cal(i,X0);
        if(B==0) A=1;
        if(ansA*B>A*ansB||(ansA*B==A*ansB&&h[ans]<h[i])) {
            ansA=A,ansB=B,ans=i;
        }
    }
    cout<<ans<<endl;
    while(m--) {
        cin>>s>>x;
        cal(s,x);
        cout<<A<<" "<<B<<endl;
    }
    return 0;
}

5702 Count The Repetitions
显然， $conn(conn(s_{2},n_{2}),m)=conn(s_{2},n_{2}m)$
为了方便讨论，我们先令 $n_{1}$ 为 $\infty$
状态表示：
F[i,j]表示从 $s_{1}[i]$ 开始，至少需要多少字符，能够生成 $conn(s_{2},2^{j})$
转移方程：
$F[i,j]=F[i,j-1]+F[(i+F[i,j-1])mod|s_{1}|,j-1]$
边界：
$F[i,0]$ 为从 $s_{1}[i]$ 生成 $s_{2}$ 至少需要多少字符，由于 $s_{1}$ 和 $s_{2}$ 长度很短，这里可以使用朴素计算，其中 $1\leq i \leq n$
目标：准备拼凑答案状态
1 枚举起始拼接位置x
1 倒序枚举所有2的整数次幂，并初始化答案为ans=0
2 若 $x+F[x\;mod\;|s_{1}|,k]\leq |s_{1}|*n_{1}$ ，则令 $\;x=x+F[x\;mod\;|s_{1}|,k],ans=ans+2^{k}$
3 最终的ans即为所求
时间复杂度： $O(nlogn)$
代码如下

/*

*/
#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>
#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=100+5;
const int INF=0x3f3f3f3f;
int n1,n2,ans,f[maxn][25],t;
string s1,s2;
int main() {
    ios::sync_with_stdio(false);
//  freopen("Count The Repetitions.in","r",stdin);
    while(cin>>s2>>n2>>s1>>n1){
        t=log(s1.size()*n1/s2.size())/log(2)+1,ans=0;
        memset(f,0,sizeof(f));
        bool flag=true;
        for(int i=0;i<s1.size();i++){
            int pos=i;
            for(int j=0;j<s2.size();j++){
                int cnt=0;
                while(s1[pos]!=s2[j]){
                    pos=(pos+1)%s1.size();
                    if(++cnt>=s1.size()){
                        cout<<0<<endl;
                        flag=false;
                        break;
                    }
                }
                if(!flag) break;
                pos=(pos+1)%s1.size();
                f[i][0]+=cnt+1;
            }
            if(!flag) break;
        }
        if(!flag) continue;
        //f[i][j]表示从s1[i]开始至少需要多少字符（假设s1无限循环），能够拼成s2循环2^j后的结果 
        for(int j=1;j<=t;j++){
            for(int i=0;i<s1.size();i++){
                f[i][j]=f[i][j-1]+f[(i+f[i][j-1])%s1.size()][j-1];
            }
        }
        for(int i=0;i<s1.size();i++){
            int x=i,ans1=0;
            for(int j=t;j>=0;j--){
                if(x+f[x%s1.size()][j]<=s1.size()*n1){
                    x+=f[x%s1.size()][j];
                    ans1+=(1<<j);
                }
            }
            ans=max(ans,ans1);
        }
        cout<<ans/n2<<endl;
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

题目	状态转移方程示例	优化方式	转移方程特点	对应具体策略
LCIS	$F[i,j]=max\left\{\begin{matrix}F[i-1,j] \;if \; A[i] \neq B[j]& \\ F[i,k] \; if \; A[i]=B[j] ,0\leq k < j ,B[k]<A[i]& \end{matrix}\right.$	数据结构优化DP	决策集合k只扩大，不缩小	使用一个变量维护最值，不断与新加入集合的元素比较
POJ 3171	$F[b_{i}]=\min_{a_{i}-1\leq x < b_{i}}\left\{F[x]\right\}+c_{i}$	同上	决策集合上界不断增大，下界不明显，同时需要支持查询最小值操作	运用线段树维护F数组
HDOJ 5542	$F[i,j]=\sum_{k<j\;并且\;A_{k}<A{j}}\left\{F[i-1,k]\right\}$	同上	决策集合区之间为有两个限制条件	用DP循环顺序保证一个条件满足，在坐标轴上建立以F数组的状态为值的树状数组维护前缀和
最大子序和	$ans=\max_{1\leq i\leq n}\left\{S[i]-\min_{i-M\leq j \leq i-1}\left\{S[j]\right\}\right\}$	单调队列优化DP	决策集合j的上下界同时在增大	利用单调队列维护 $\min_{i-M\leq j \leq i-1}\left\{S[j]\right\}$ 每个决策只会进队出队一次
POJ 1821	$F[i,j]=P_{i}j+\max_{j-L_{i}\leq k \leq S_{i}-1}\left\{F[i-1,k]-P_{i}k \right\}，其中j\geq S_{i}$	同上	在每一个i循环内部，决策集合上界不变，下界不断增大	维护一个 $F[i-1.k]-P_{i}*k$ 单调递减的队列
多重背包	$F[u+pV_{i}]=\max_{p-C_{i}\leq k\leq p-1}\left\{F[u+kV_{i}]+(p-k)*W_{i}\right\}$	同上	决策集合k的上下界同时在减小	维护一个 $F[u+kV_{i}]-kW_{i}$ 单调递减的单调队列
任务安排2	$F[i]=\min_{0\leq j<i}\left\{F[j]-(S+sumT[i])sumC[j]\right\}+sumT[i]sumC[i]+S*sumC[n]$	斜率优化DP	递推式中含有i*j的项	维护一个相邻两点线段斜率递增的单调队列
NOI 2009 BZOJ1563	$F[i]=\min_{0\leq j<i}\left\{F[j]+\|(sum[i]-sum[j])+(i-j-1)-L\|^{P}\right\}$	四边形不等式优化DP	递推式中含有i、j的高次项，符合四边形不等式	用一个队列维护决策三元组，每次二分查找有序的插入位置

上面公式的放大版

LCIS

$F[i,j]=max\left\{\begin{matrix}F[i-1,j] \;if \; A[i] \neq B[j]& \\ F[i,k] \; if \; A[i]=B[j] ,0\leq k < j ,B[k]<A[i]& \end{matrix}\right.$

POJ 3171

$F[b_{i}]=\min_{a_{i}-1\leq x < b_{i}}\left\{F[x]\right\}+c_{i}$

HDOJ 5542

$F[i,j]=\sum_{k<j\;并且\;A_{k}<A{j}}\left\{F[i-1,k]\right\}$

最大子序和

$ans=\max_{1\leq i\leq n}\left\{S[i]-\min_{i-M\leq j \leq i-1}\left\{S[j]\right\}\right\}$

POJ 1821

$F[i,j]=P_{i}*j+\max_{j-L_{i}\leq k \leq S_{i}-1}\left\{F[i-1,k]-P_{i}*k \right\}，其中j\geq S_{i}$

多重背包

$F[u+p*V_{i}]=\max_{p-C_{i}\leq k\leq p-1}\left\{F[u+k*V_{i}]+(p-k)*W_{i}\right\}$

任务安排2

$F[i]=\min_{0\leq j<i}\left\{F[j]-(S+sumT[i])*sumC[j]\right\}+sumT[i]*sumC[i]+S*sumC[n]$

NOI 2009 BZOJ1563

$F[i]=\min_{0\leq j<i}\left\{F[j]+\|(sum[i]-sum[j])+(i-j-1)-L\|^{P}\right\}$

数据结构优化DP

倍增优化DP从状态入手，优化状态定义。
而接下来的四种DP优化方法则着眼于如何优化转移方程，换句话说，就是如何高效的维护一个有特定秩序的候选集合，具体详见上面的总表。

例题

POJ2376 Cleaning Shifts
状态表示：F[x]表示覆盖[L,x]需要花费的最小代价
余下内容实质上时POJ 3171的简化版
这里提供两种代码，method_1为贪心，method_2为线段树优化DP

/*

*/
#define method_2
#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>
#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=25000+5;
const int INF=0x3f3f3f3f;
struct node {
    int x,y;
    bool operator<(const node &h)const {
        return (x<h.x)||(x==h.x&&y<h.y);
    }
} seq[maxn];
int n,T,ans=0;
int main() {
    ios::sync_with_stdio(false);
    //freopen("Cleaning Shifts.in","r",stdin);
    cin>>n>>T;
    for(int i=1; i<=n; i++) cin>>seq[i].x>>seq[i].y;
    sort(seq+1,seq+n+1);
//  for(int i=1;i<=n;i++) cout<<seq[i].x<<" "<<seq[i].y<<endl;
    int temp=0,r=0;
    for(int i=1; i<=n; i++) {
        if(seq[i].x>temp+1) {
            cout<<-1;
            return 0;
        }
        r=seq[i].y;
        while(i<n&&seq[i+1].x<=temp+1) {
            i++;
            r=max(r,seq[i].y);
        }
        temp=r;
    //  cout<<i<<" "<<temp<<endl;
        ans++;
        if(temp>=T) break;
    }
    if(temp<T) {
        cout<<-1;
        return 0;
    }
    cout<<ans;
    return 0;
}
#endif
#ifdef method_2
/*
线段树 POJ 3171 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#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=25000+5;
const int maxL=1e6+5;
const int INF=0x3f3f3f3f;
struct node {
    int x,y;
    bool operator<(const node &h)const {
        return (x<h.x)||(x==h.x&&y<h.y);
    }
} seq[maxn];
struct SegmentTree{
    int l,r,dat;
}tr[maxL<<2];
int n,T,ans=0;
void build(int rt,int l,int r){
    tr[rt].l=l,tr[rt].r=r;
    if(l==r){
        tr[rt].dat=INF;
        return;
    }
    int mid=l+r>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    tr[rt].dat=min(tr[rt<<1].dat,tr[rt<<1|1].dat);
}
void change(int rt,int pos,int v){
    if(tr[rt].l==tr[rt].r){
        tr[rt].dat=min(v,tr[rt].dat);
        return;
    }
    int mid=tr[rt].l+tr[rt].r>>1;
    if(pos<=mid) change(rt<<1,pos,v);
    else change(rt<<1|1,pos,v);
    tr[rt].dat=min(tr[rt<<1].dat,tr[rt<<1|1].dat);
}
int ask(int rt,int l,int r){
    if(tr[rt].l>=l&&tr[rt].r<=r) return tr[rt].dat;
    int mid=tr[rt].l+tr[rt].r>>1;
    int val=INF;
    if(mid>=l) val=min(val,ask(rt<<1,l,r));
    if(mid<r) val=min(val,ask(rt<<1|1,l,r));
    return val;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("Cleaning Shifts.in","r",stdin);
    cin>>n>>T;
    for(int i=1; i<=n; i++) cin>>seq[i].x>>seq[i].y;
    sort(seq+1,seq+n+1);
    build(1,0,T);
    int temp=0;
    change(1,0,0);//f[0]=0
    for(int i=1;i<=n;i++){
        if(temp+1<seq[i].x){
            cout<<-1;
            return 0;
        }
        int val=ask(1,seq[i].x-1,seq[i].y);
        change(1,seq[i].y,val+1);
        temp=max(temp,seq[i].y);
    }
//  cout<<ask(1,T,T)<<endl;
    if(temp<T){
        cout<<-1;
        return 0;
    }
    int ans=INF;
    for(int i=1;i<=n;i++){
        if(seq[i].y>=T) ans=min(ans,ask(1,T,seq[i].y));
    }
    cout<<ans;
    return 0;
}
#endif
#ifdef method_3
/*

*/

#endif

单调队列优化DP

单调队列优化DP的基本形式如下
$F[i]=\min_{L(i)\leq j \leq R(i)}\left\{F[j]+val(i,j)\right\}$
其中L(i)和R(i)是关于i的一次函数，他们限制了j的范围，同时上下界变化具有单调性。val(i,j)是关于i和j的多项式函数，我们解题时，通常把它分成两部分，第一部分只包含i，第二部分只包含j，我们通过使用单调对了维护第二部分的单调性。
PS：val(i,j)需满足每一项只和i或者j有关

例题

POJ1821 Fence
首先按照 $S_{i}$ 排序，这就保证了每个工匠粉刷的木板一定在上一个工匠粉刷的木板之后，于是可以确定DP顺序。
状态表示：F[i,j]表示安排前i个木匠粉刷前j块木板的最优解
转移方程：
决策1 第i个木匠不刷 $F[i,j]=F[i-1,j]$
决策2 第j个木板不刷 $F[i,j]=F[i,j-1]$
决策3 第i个木匠刷第k+1...第j块木板
$F[i,j]=\max_{j-L_{i}\leq k \leq S_{i}-1}\left\{F[i-1,k]-P_{i}*(j-k) \right\}，其中\;j\geq S_{i}$
将状态、决策分离，即分开包含j的项和包含k的项，得到如下方程
$F[i,j]=P_{i}*j+\max_{j-L_{i}\leq k \leq S_{i}-1}\left\{F[i-1,k]-P_{i}*k \right\}，其中\;j\geq S_{i}$
考虑两个决策 $k_{1}$ 和 $k_{2}$ ， $k_{1}<k_{2}$ ，则 $k_{1}$ 会比 $k_{2}$ 跟早离开决策集合，若此时 $F[i-1,k_{1}]-P_{i}*k_{1}\leq F[i-1,k_{2}]-P_{i}*k_{2}$ ，那么 $k_{1}$ 就是无用决策。
因此维护一个 $F[i-1,k]-P_{i}*k$ 降序的单调队列即可
代码如下

/*

*/
#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>
#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=16000+5;
const int maxm=100+5;
const int INF=0x3f3f3f3f;
int q[maxn],f[maxm][maxn],n,m;
struct node {
    int L,P,S;
    bool operator<(const node &h)const {
        return S<h.S;
    }
} seg[maxm];
int cal(int i,int k) {
    return f[i-1][k]-seg[i].P*k;
}
int main() {
    ios::sync_with_stdio(false);
    freopen("Fence.in","r",stdin);
    cin>>n>>m;
    for(int i=1; i<=m; i++) cin>>seg[i].L>>seg[i].P>>seg[i].S;
    sort(seg+1,seg+m+1);
    for(int i=1; i<=m; i++) {
        int l=1,r=0;
        for(int k=max(seg[i].S-seg[i].L,0); k<=seg[i].S-1; k++) {
            while(l<=r&&cal(i,q[r])<cal(i,k)) r--;
            q[++r]=k;
        }
        for(int j=1; j<=n; j++) {
            f[i][j]=max(f[i][j],max(f[i-1][j],f[i][j-1]));
            if(j>=seg[i].S) {
                while(l<=r&&q[l]<j-seg[i].L) l++;
                if(l<=r) f[i][j]=max(f[i][j],seg[i].P*j+cal(i,q[l]));
                /*
                这里不要这两句话，k是决策而j是状态 所以更新j的状态时，用单调队列维护k的决策单调性
                j作为状态 是不可以进入维护决策k的单调队列的 
                话句话说 就是 k的范围中 只有下界和j有关 而上界与i有关（在循环内部，可将i视为常量，所以不用增加新决策） 
                while(l<=r&&cal(i,q[r])<cal(i,j)) r--;
                q[++r]=j;
                */
            }
        }
    }
    cout<<f[m][n];
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

另外，我们做单调队列优化DP题目的时候，需要格外注意是否需要在内层循环向队列中插入新的决策（对比POJ 1821和多重背包）。同时，有些单调队列的队头不一定是单调决策，这时我们通常会同时维护一个二叉堆来辅助计算（POJ 3017）

斜率优化DP

若在 $F[i]=\min_{L(i)\leq j \leq R(i)}\left\{F[j]+val(i,j)\right\}$ 中，存在val(i,j)有一项是i和j的乘积形式，那么就需要用斜率优化。
对于符合这样特性的递推式，我们往往会将递推式作为一次函数的形式，即j关于i的方程——F[i]=k*F[j]+c
然后我们维护一个至少含有两个元素的单调队列，则通常情况下，插入新元素的时候，队尾元素的前一个元素，队尾元素和新元素三者会构成一个“凸壳”，凸壳的中心点往往是无用决策，可以排除。

例题

5A01 任务安排1
状态表示：F[i,j]表示前i个任务分成j批的最小费用，同时求出T数组和C数组的前缀和sumT和sumC
转移方程： $F[i,j]=\min_{0\leq k<i}\left\{F[k,j-1]+(S*j+sumT[i])*(sumC[i]-sumC[k])\right\}$
目前时间复杂度： $O(n^{3})$
考虑优化，进行如下状态定义
状态表示：F[i]表示前i个任务的最小费用，同时求出T数组和C数组的前缀和sumT和sumC
转移方程： $F[i]=\min_{0\leq j<i}\left\{F[j]+sumT[i]*(sumC[i]-sumC[j])+S*(sumC[n]-sumC[j])\right\}$
方程解释：我们不直接得到执行一批任务时，机器启动次数，但是我们直到机器因为执行这批任务而花费启动时间S，因此会累加到最后所有任务完成的时间上。S*(sumC[n]-sumC[j])就表示因为这批任务，机器的启动时间会对j+1之后的所有任务产生影响。这是一种经典的“费用提前计算”的思想。
用这个转移方程，目前时间复杂度： $O(n^{2})$
已经能够通过本题，代码如下

/*

*/
#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>
#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=5000+5;
const int INF=0x3f3f3f3f;
int n,s,t[maxn],c[maxn],f[maxn];
int main() {
    ios::sync_with_stdio(false);
    //freopen("任务安排1.in","r",stdin);
    cin>>n>>s;
    for(int i=1;i<=n;i++) cin>>t[i]>>c[i],t[i]+=t[i-1],c[i]+=c[i-1];
    memset(f,INF,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            f[i]=min(f[i],f[j]+t[i]*(c[i]-c[j])+s*(c[n]-c[j]));
        }
    }
    cout<<f[n];
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

POJ1180 任务安排2
本题数据经过加强，上面的方法在部分评测机上无法通过（事实上由于CH的评测机跑得快，如果直接用上面的代码，会600ms卡过去）
下面介绍如何用斜率优化来加速递推
我们把上面的转移方程变形，将常数项，与i有关的项，与j有关的项，与i、j都有关的项分离，得到如下方程
$F[i]=\min_{0\leq j<i}\left\{F[j]-(S+sumT[i])*sumC[j]\right\}+sumT[i]*sumC[i]+S*sumC[n]$
去掉min函数，将j看作变量移到左边得到
$F[j]=(S+sumT[i])*sumC[j]+F[i]-sumT[i]*sumC[i]+S*sumC[n]$
这是一条sumC[j]为变量，(S+sumT[i])为斜率，F[i]-sumT[i]sumC[i]+SsumC[n]为截距，F[j]为纵坐标的直线.
也就是说，每个决策对应着平面直角坐标系中的一个点(sumC[j],F[j])，斜率相对为定值，截距未知，而当截距最小化的时候，F[i]自然最小。
因此我们考虑任意三个决策点j1,j2,j3，讨论何时j2会可能成为最优决策。
由于斜率大于0，所以若线段j1j2和线段j2j3构成上凸结构，j2不可能成为最优决策。所以若线段j1j2和线段j2j3构成下凸结构，j2可能成为最优决策。
即j2需要满足
$\frac{F[j_{2}]-F[j_{1}]}{sumC[j_{2}]-sumC[j_{1}]}<\frac{F[j_{3}]-F[j_{2}]}{sumC[j_{3}]-sumC[j_{2}]}$
因此我们维护一个相邻两点线段斜率递增的单调队列即可（具体地说，就是维护队首元素和队首元素的下一个元素构成线段斜率大于S+sumT[i]。同时维护队尾元素和队尾元素的前一个元素和新元素满足斜率单调性）
代码如下

/*
O(n)
10ms
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#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=10000+5;
const int INF=0x3f3f3f3f;
int n,s,t[maxn],c[maxn],f[maxn],q[maxn],l=0,r=1;
int main() {
    ios::sync_with_stdio(false);
    //freopen("任务安排2.in","r",stdin);
    cin>>n>>s;
    for(int i=1;i<=n;i++) cin>>t[i]>>c[i],t[i]+=t[i-1],c[i]+=c[i-1];
    memset(f,INF,sizeof(f));
    f[0]=0;
    q[++l]=0;//f[0]=0
    for(int i=1;i<=n;i++){
        //由于是斜率优化，队列维护的是相邻两个元素的关系 所以队列至少要有两个元素 即l<r 
        //同时化斜率比值为乘法 防止精度误差 
        while(l<r&&(f[q[l+1]]-f[q[l]])<=(s+t[i])*(c[q[l+1]]-c[q[l]])) l++;
        f[i]=f[q[l]]-(s+t[i])*c[q[l]]+t[i]*c[i]+s*c[n];
        while(l<r&&(f[q[r]]-f[q[r-1]])*(c[i]-c[q[r]])>=(f[i]-f[q[r]])*(c[q[r]]-c[q[r-1]])) r--;
        q[++r]=i;
    }
    cout<<f[n];
    return 0;
}

四边形不等式优化DP

若在 $F[i]=\min_{L(i)\leq j \leq R(i)}\left\{F[j]+val(i,j)\right\}$ 中，存在val(i,j)有一项是i和j的若干高次项乘积形式，那么就需要考虑能否使用四边形不等式优化。（例题：NOI 2009 BZOJ 1563）

最后编辑于：2019.09.29 15:16:58

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 216,651评论 6赞 501
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,468评论 3赞 392
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 162,931评论 0赞 353
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,218评论 1赞 292
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,234评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,198评论 1赞 299
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,084评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,926评论 0赞 274
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,341评论 1赞 311
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,563评论 2赞 333
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,731评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,430评论 5赞 343
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,036评论 3赞 326
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,676评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,829评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,743评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,629评论 2赞 354