优化dp

本文主要是介绍优化dp，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

单调队列优化dp

单调队列

单调队列是一种特殊的双端队列，其内部元素具有单调性。常见有最大队列和最小队列两种单调队列，其内部元素分别是单调递减和单调递增的。
支持两种操作
-插入：如果新元素从队尾插入后会破坏其单调性，则删除队尾元素，直到插入后不再破坏单调性为止，再将其插入单调队列。
获取最大（最小）值：访问队首元素。

可优化的dp形式

\(eg:\) \(f[i] = min(f[j] + val(i,j)) (Li \leq j \leq Ri)\)

其中Li和Ri都是关于变量i的一次函数，限制了j的取值范围，并保证上下界具有单调性
能把\(val(i,j)\)分成两部分，一部分仅和\(i\)相关，一部分仅和\(j\)相关，
对于每个\(i\)，无论采取哪个\(j\)作为最优策略，第一部分的值都是相等的，可以选出最优决策更新\(f[i]\)时再进行计算、累加，
当\(i\)发生变化时，第二部分的值不会发生变化，从而保证原来较优的决策，我们可以在队列中维护第二部分的单调性，及时排除不可能的决策，使得\(dp\)高效的进行

基础思想

参考例题P1886 滑动窗口 /【模板】单调队列

点击查看代码

#include <iostream>
#include <cstdio>
#define Re register int
using namespace std;
inline int read(){
    int x = 0, f = 1; char c;
    while(!isdigit(c = getchar())) if(c == '-') f = -1;
    do x = (x << 1) + (x << 3) + (c ^ 48); while(isdigit(c = getchar()));
    return x * f;
}
const int N = 1e6+6;
int n,k,a[N],q[N],l,r;
int main(){
    // freopen("T.in","r",stdin);
    // freopen("T.out","w",stdout);
    n = read(); k = read();
    for(Re i = 1; i <= n; ++i) a[i] = read();
    l = 1; r = 0;
    for(Re i = 1; i < k; ++i){
        while(l <= r && a[q[r]] > a[i]) r--;
        q[++r] = i;
    }
    for(Re i = k; i <= n; ++i){
        while(l <= r && i - q[l] + 1 > k) ++l;
        while(l <= r && a[q[r]] > a[i]) --r;
        q[++r] = i;
        printf("%d ",a[q[l]]);
    }
    putchar('\n');
    l = 1;r = 0;
    for(Re i = 1; i < k; ++i){
        while(l <= r && a[q[r]] < a[i]) r--;
        q[++r] = i;
    }
    for(Re i = k; i <= n; ++i){
        while(l <= r && i - q[l] + 1 > k) ++l;
        while(l <= r && a[q[r]] < a[i]) --r;
        q[++r] = i;
        printf("%d ",a[q[l]]);
    }
    putchar('\n');
    return 0;
}

题

股票交易

列dp方程:f[i][j]表示前i天手里有j股的时候所能赚的最多的钱

考虑转移:

不买不卖
\(f[i][j] = f[i - 1][j]\)
买入
\(f[i][j] = f[i - W - 1][k] - (j - k) * Ap[i], k >= j - As[i]\)
卖出
\(f[i][j] = f[i - W - 1][k] + (k - j) * Bp[i], k <= j + Bs[i]\)
直接买
\(f[i][j] = -j * Ap[i]\)

考虑优化：
对于买入的转移，发现j和\(j-1\)是有重合部分的，类似于滑动窗口的变化趋势
且\(dp\)式子有只与决策点\(k\)有关的式子，所以可以单调队列进行优化
卖出同理

点击查看代码

#include <iostream>
#include <cstdio>
#include <cstring>
#define Re register int
using namespace std;
inline int read(){
    int x = 0, f = 1; char c;
    while(!isdigit(c = getchar())) if(c == '-') f = -1;
    do x = (x << 1) + (x << 3) + (c ^ 48); while(isdigit(c = getchar()));
    return x * f;
}
const int N = 2004;
int T,MaxP,W,Ap[N],Bp[N],As[N],Bs[N],f[N][N];
int l,r,q[N];
int main(){
    // freopen("T.in","r",stdin);
    // freopen("T.out","w",stdout);
    T = read(); MaxP = read(); W = read();
    for(Re i = 1; i <= T; ++i){
        Ap[i] = read(); Bp[i] = read();
        As[i] = read(); Bs[i] = read();
    }
    memset(f,-0x3f,sizeof(f));
    for(Re i = 1; i <= T; ++i){
        for(Re j = 0; j <= As[i]; ++j) f[i][j] = max(f[i][j],-Ap[i] * j);
        for(Re j = 0; j <= MaxP; ++j) f[i][j] = max(f[i][j],f[i - 1][j]);
        if(i <= W) continue;
        l = 1; r = 0;
        for(Re j = 0; j <= MaxP; ++j){
            while(l <= r && q[l] < j - As[i]) ++l;
            if(l <= r) f[i][j] = max(f[i][j],f[i - W - 1][q[l]] - j * Ap[i] + q[l] * Ap[i]);
            while(l <= r && f[i - W - 1][q[r]] + q[r] * Ap[i] <= f[i - W - 1][j] + j * Ap[i]) --r;
            q[++r] = j;
        }
        l = 1; r = 0;
        for(Re j = MaxP; j >= 0; --j){
            while(l <= r && q[l] > j + Bs[i]) ++l;
            if(l <= r) f[i][j] = max(f[i][j],f[i - W - 1][q[l]] + q[l] * Bp[i] - j * Bp[i]);
            while(l <= r && f[i - W - 1][q[r]] + q[r] * Bp[i] <= f[i - W - 1][j] + j * Bp[i]) --r;
            q[++r] = j;
        }
    }
    int ans = -0x3f3f3f3f;
    for(Re i = 0; i <= MaxP; ++i) ans = max(ans,f[T][i]);
    printf("%d\n",ans);
    return 0;
}

瑰丽华尔兹

设\(f[i][j][t]\)为第\(t\)个时间在\((i,j)\)的最大滑动距离
转移\(f[i][j][t] = max(f[i'][j'][t - 1] + dis,f[i][j][t-1])\)
\(Then\) \(you\) \(will\) \(get\) \(MLE.\)

一段时间段内的滑动方向一致
设\(f[i][j][k]\)为\(k\)个时间段后在\((i,j)\)时的最大滑动距离
转移\(f[i][j][k] = max(f[i'][j'][k-1] + dis,f[i][j][k])\)
\(O(kn^3)\)
\(Then\) \(you\) \(will\) \(get\) \(TLE.\)

考虑优化：
每个时间段内都是在同一列或者同一行滑动，联想到滑动窗口，可以进行单调队列优化

#include <iostream>
#include <cstring>
#include <cstdio>
#define Re register int
using namespace std;
inline int read(){
    int x = 0, f = 1; char c;
    while(!isdigit(c = getchar())) if(c == '-') f = -1;
    do x = (x << 1) + (x << 3) + (c ^ 48); while(isdigit(c = getchar()));
    return x * f;
}
const int N = 203;
int dx[5] = {0,-1,1,0,0}, dy[5] = {0,0,0,-1,1};
int n,m,x,y,K,f[N][N],l,r,ans;
char Map[N][N];
struct Node{int dp,pos;}q[N];
void solve(int x,int y,int len,int d){
    l = 1; r = 0;
    for(Re i = 1; ; ++i, x += dx[d], y += dy[d]){
        if(x <= 0 || x > n || y <= 0 || y > m) break;
        if(Map[x][y] == 'x') l = 1, r = 0;
        else{
            while(l <= r && q[r].dp + i - q[r].pos <= f[x][y]) --r;
            q[++r] = (Node){f[x][y],i};//这里需要先加入队尾，这样保证队列里的值都是上一个时间段的
            while(l <= r && i - q[l].pos > len) ++l;
            f[x][y] = max(f[x][y],q[l].dp + i - q[l].pos);
            ans = max(f[x][y],ans);
        }
    }
}
int main(){
    // freopen("T.in","r",stdin);
    // freopen("T.out","w",stdout);
    n = read(); m = read(); x = read(); y = read(); K = read();
    for(Re i = 1; i <= n; ++i) scanf(" %s ",Map[i] + 1);
    memset(f,-0x3f,sizeof(f));
    f[x][y] = 0;
    for(Re i = 1; i <= K; ++i){
        int s = read(), t = read(), d = read();
        int len = t - s + 1;
        if(d == 1) for(Re j = 1; j <= m; ++j) solve(n,j,len,d);
        if(d == 2) for(Re j = 1; j <= m; ++j) solve(1,j,len,d);
        if(d == 3) for(Re j = 1; j <= n; ++j) solve(j,m,len,d);
        if(d == 4) for(Re j = 1; j <= n; ++j) solve(j,1,len,d);
    }
    printf("%d\n",ans);
    return 0;
}

斜率优化dp

可优化的dp形式

\(eg: f[i] = min(f[j] + val(i,j))\)
其中\(val(i,j)\)既与\(i\)相关又与\(j\)相关，比如\(2 * x[i] * x[j]\)
此时需要用到斜率优化
两点间连线斜率:\(\frac{y1 - y2}{x1 - x2}\)

(From here)

算法核心

例题引入

【APIO2010】特别行动队
不难得出
\(dp[i] = max(dp[j] + a \times (sumi - sumj) ^ 2 + b \times (sumi- sumj) + c)\)
其中\(j\)作为决策点，\(i\)的值固定，所以把只与\(i\)相关的量视为常量
剩下的式子为 \(dp[j] - 2 \times a \times sumi \times sumj + a \times sumj^2 - b \times sumj\)
对于式子中只与\(j\)相关的项，无论\(i\)如何变这个值都是不变的。所以可以将这些项的和压缩为一个函数\(y\)
令\(y(j) = dp[j] + a \times sumj^2 - b \times sumj\)
式子变为\(y(j) + (-2 \times a \times sumi) \times sumj\)
令\(k(i) = -2 \times a \times sumi\)，式子变为\(y(j) + k(i) \times sumj\)

从上述可得，如果两个相连的直线的斜率不大于\(k = 2 \times a \times sumi\),那么前面那个店对应的j就一定不是最优决策点；反之，后面那个点就一定不是最优决策点。
由此推广到更多的点：如果前两个点的斜率大于后两个点的斜率，那么把中间的点删去
因为此题中a 是负的\(,k\)一定是小于\(0\)的，所以维护上凸包

#include <iostream>
#include <cstdio>
#define int long long
#define Re register int
#define K(i) (2 * a * sum[i])
#define X(i) (sum[i])
#define Y(i) (f[i] + a * sum[i] * sum[i] - b * sum[i])
using namespace std;
inline int read(){
    int x = 0, f = 1; char c;
    while(!isdigit(c = getchar())) if(c == '-') f = -1;
    do x = (x << 1) + (x << 3) + (c ^ 48); while(isdigit(c = getchar()));
    return x * f;
}
const int N = 1e6+6;
int n,sum[N],a,b,c,l,r,q[N],f[N];
double slope(int i,int j){
    return 1.0 * (Y(i) - Y(j)) / (X(i) - X(j));
}
signed main(){
    // freopen("T.in","r",stdin);
    // freopen("T.out","w",stdout);
    n = read(); a = read(); b = read(); c = read();
    for(Re i = 1; i <= n; ++i) sum[i] = read(), sum[i] += sum[i - 1];
    // for(Re i = 1; i <= n; ++i) cout << sum[i] << " "; cout << endl;
    for(Re i = 1; i <= n; ++i){
        while(l < r && slope(q[l],q[l + 1]) > K(i)) ++l;
        f[i] = -K(i) * X(q[l]) + Y(q[l]) + a * sum[i] * sum[i] + b * sum[i] + c;
        while(l < r && slope(q[r - 1],q[r]) <= slope(q[r],i)) --r;
        //因为k<0所以维护的是上凸壳
        q[++r] = i;
    }
    printf("%lld\n",f[n]);
    return 0;
}

线段树优化dp

这篇关于优化dp的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

优化dp

单调队列优化dp

单调队列

可优化的dp形式

基础思想

题

股票交易

瑰丽华尔兹

斜率优化dp

可优化的dp形式

算法核心

例题引入

线段树优化dp

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯