优化dp

1.单调队列优化dp

单调队列优化=提出与内层循环无关的数据，把剩余有关最大值最小值的问题用单调队列维护，要求转移范围是滑动的。

例题

1.CF372C Watching Fireworks is Fun

设 \(dp(i,j)\) 表示放第 \(i\) 个烟花时，在位置 \(j\) 所得到的开心值的最大值。

我们设 \(dx=d\times (t_i-t_{i-1})\)，也就代表可以移动到 \(j\) 的最大距离，不难得出转移方程：

因为 \(b_i\) 累加的结果不变，所以可以在转移方程中删去，在结果中加上 \(sum_b\)，也就化简有：

这里 \(-|a_i-j|\) 的结果与 \(k\) 是无关的，故可以提出。而这个值实际为负，可以维护其绝对值的最小值。不难发现，我们每个值，都是从 \([j-dx,j+dx]\) 之间的最值得到的，考虑单调队列优化。

只需要做如下两种操作：

• 队首元素是当前最优且最前，如果超出范围需要弹出
• 队尾元素是可能最优且最后，如果没有新入队的优需要弹出

但是我们的单调队列只能支持到 \(j\) 的范围，所以把这个区间拆分开，正反各跑一遍。

int main(){
    n=read(),m=read(),d=read();
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=m;i++){
        a[i]=read(),b[i]=read(),t[i]=read();
        sum+=b[i];
    }
    for(int i=1;i<=n;i++){
        dp[1][i]=Abs(a[1]-i);
    }
    for(int i=2;i<=m;i++){
        ll dx=(t[i]-t[i-1])*d;
        memset(dp[i&1],0x3f,sizeof(dp[i&1]));
        head=1,tail=0;
        for(int j=1;j<=n;j++){
            while(head<=tail&&q[head]dp[i&1^1][j]) tail--;
            q[++tail]=j;
            dp[i&1][j]=Min(dp[i&1][j],dp[i&1^1][q[head]]+Abs(a[i]-j));
        }
        head=1,tail=0;
        for(int j=n;j>=1;j--){
            while(head<=tail&&q[head]>j+dx) head++;
            while(head<=tail&&dp[i&1^1][q[tail]]>dp[i&1^1][j]) tail--;
            q[++tail]=j;
            dp[i&1][j]=Min(dp[i&1][j],dp[i&1^1][q[head]]+Abs(a[i]-j));
        }
    }
    ans=0x3f3f3f3f3f3f3f3f;
    for(int i=1;i<=n;i++){
        ans=Min(ans,dp[m&1][i]);
    }
    printf("%lld\n",sum-ans);
    return 0;
} 

2.P2569 SCOI2010 股票交易

自然是 \(dp(i,j)\) 表示第 \(i\) 天持有 \(j\) 只股票的最高收益，不难发现有，不操作、买与卖三种状态。

不操作的转移十分朴素，\(dp(i,j)=\max(dp(i,j),dp(i-1,j))\)

其实买卖的操作无需枚举 \(i-w-1\) 及以前的天数，因为不操作的情况已经转移到了后一天，因此从 \(dp(i-w-1,k)\) 转移即可，就能得到两个转移方程。

买：

提出与 \(k\) 的项无关得到：

卖：

同理化简，可以得到：

明显括号里面的是可以用单调队列优化的。

int main(){
    n=read(),m=read(),w=read();
    for(int i=1;i<=n;i++){
        ap[i]=read(),bp[i]=read(),as[i]=read(),bs[i]=read();
    }
    memset(dp,~0x3f,sizeof(dp));
    for(int i=0;i<=n;i++){
        dp[i][0]=0;
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=as[i];j++){
            dp[i][j]=-1*j*ap[i];
        }
        for(int j=0;j<=m;j++){
            dp[i][j]=max(dp[i][j],dp[i-1][j]);
        }
        if(i>=w+1){
            head=1,tail=0;
            for(int j=0;j<=m;j++){
                while(head<=tail&&q[head]=dp[i-w-1][q[tail]]+ap[i]*q[tail]) tail--;
                q[++tail]=j;
                if(head<=tail) dp[i][j]=max(dp[i][j],dp[i-w-1][q[head]]-ap[i]*(j-q[head]));
            }
            head=1,tail=0;
            for(int j=m;j>=0;j--){
                while(head<=tail&&q[head]>j+bs[i]) head++;
                while(head<=tail&&dp[i-w-1][j]+bp[i]*j>=dp[i-w-1][q[tail]]+bp[i]*q[tail]) tail--;
                q[++tail]=j;
                if(head<=tail) dp[i][j]=max(dp[i][j],dp[i-w-1][q[head]]+bp[i]*(q[head]-j));
            }
        }
    }
    int ans=-1;
    for(int i=0;i<=m;i++){
        ans=max(ans,dp[n][i]);
    }
    printf("%d\n",ans);
    return 0;
}

3.P2254 NOI2005 瑰丽华尔兹

忽略起始位置等等，每个区间都在整个地图中每行或每列用单调队列d优化p，滚动数组减少空间。

4.P2627 Mowing the Lawn G

常规单调队列优化即可。

2.斜率优化dp

讲真很难的优化方式。

简单说一下思想：当递推式中出现了形如 \(a[i]\times b[j]+c[i]+d[j]\) 的式子时，显然单调队列优化是不可行的，因此我们把其化作一次函数 \(b=y-kx\) 的形式，就能得到一个凸包，用单调队列去维护凸包。

例题

1.P3195 HNOI2008 玩具装箱

先求前缀和 \(pre\)，直接可以得到的递推式：\(dp_i=\min_{j=1}^{i-1}\{dp_j+(pre_i-pre_j+i-j-1-l)^2\}\)

设 \(sum_i=pre_i+1,l'=l+1\)，为方便观察去掉 \(\min\)，就能得到 \(dp_i=dp_j+(sum_i-sum_l-l')^2\)，也就有：\(dp_i=dp_j+sum_i^2+(sum_j+l')^2-2sum_isum_j-2sum_il'\)，之后移项成上述式子就有 \(dp_i-sum_i^2+2sum_il'=dp_j+(sum_j+l')^2-2sum_i\times sum_j\)，其中 \(b=dp_i-sum_i^2+2sum_il',y=dp_j+(sum_j+l')^2,k=2sum_i,x=sum_j\)。

之后我们得到了一个下凸包，让斜率在保证大于 \(k\) 的情况下尽量小，单调队列维护这个凸包。

ll n,l;
ll sum[maxn],dp[maxn];
ll q[maxn],head,tail;
inline ll X(ll i){
    return sum[i];
}
inline ll Y(ll i){
    return dp[i]+(sum[i]+l)*(sum[i]+l);
}
inline ldb slope(ll i,ll j){
    return (ldb)(Y(j)-Y(i))/(X(j)-X(i));
}
int main(){
    n=read(),l=read()+1;
    for(int i=1;i<=n;i++){
        sum[i]=read()+sum[i-1]+1;
    }
    head=1,tail=1;
    q[1]=0;
    for(int i=1;i<=n;i++){
        while(head=slope(q[tail-1],i)) tail--;
        q[++tail]=i;
    }
    printf("%lld\n",dp[n]);
    return 0;
}

2.P3628 APIO2010 特别行动队

借本题谈一谈斜率优化的常规做法。

首先还是维护前缀和 \(sum\)，正常的递推式（省略 \(\min\)）是 \(dp_i=dp_j+a(sum_i-sum_j)+b(sum_i-sum_j)+c\)，我们把式子打开，只 \(i\) 相关的移到等式左边，就能得到 \(dp_i=dp_j+asum_i^2-2asum_isum_j+asum_j^2+bsum_i-bsum_j+c\)，\(dp_i-asum_i^2-bsum_i=-2asum_isum_j+asum_j^2-bsum_j+c\)，这样就得到了 \(b=y-kx\) 形式的递推式，可以发现我们的 \(b\) 是关于 \(i\) 的，\(y\) 是关于 \(j\) 的 \(-kx\) 是与 \(i,j\) 都相关的一项，并且把前半部分当做 \(-k\)，后半部分当作 \(x\)。

之后只需要带入维护凸包即可。

int n;
int a,b,c;
ll sum[maxn],dp[maxn];
int q[maxn],head,tail;
inline ll X(int i){
    return sum[i];
}
inline ll Y(int i){
    return dp[i]+a*sum[i]*sum[i]-b*sum[i];
}
inline ll K(int i){
    return 2*a*sum[i];
}
inline ll B(int i){
    return dp[i]-a*sum[i]*sum[i]-b*sum[i]-c;
}
inline db slope(int i,int j){
    return (db)(Y(i)-Y(j))/(X(i)-X(j));
}
int main(){
    n=read();
    a=read(),b=read(),c=read();
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+read();
    }
    int head=1,tail=1;
    q[tail]=0;
    for(int i=1;i<=n;i++){
        while(headK(i)) head++;
        dp[i]=Y(q[head])-K(i)*X(q[head])+a*sum[i]*sum[i]+b*sum[i]+c;
        while(head