单调队列优化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/)高效的进行
基础思想
点击查看代码
#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
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/288327.html