成立网站公司需要什么,网站备案必须在公司注册地,1688网站店招怎么做,企业网站的搭建流程文章目录 单调队列优化dp烽火传递修剪草坪绿色通道琪露诺旅行问题Watching Fireworks is Fun瑰丽华尔兹股票交易 单调队列优化dp
文章首发于我的个人博客#xff1a;欢迎大佬们来逛逛
单调队列优化dp的建模形式#xff1a;这是窗口右滑动的情况
对于窗口左滑动的也是同理。… 文章目录 单调队列优化dp烽火传递修剪草坪绿色通道琪露诺旅行问题Watching Fireworks is Fun瑰丽华尔兹股票交易 单调队列优化dp
文章首发于我的个人博客欢迎大佬们来逛逛
单调队列优化dp的建模形式这是窗口右滑动的情况
对于窗口左滑动的也是同理。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6b43a5LW-1685532776854)(%E5%8D%95%E8%B0%83%E9%98%9F%E5%88%97%E4%BC%98%E5%8C%96dp%20dd9f82e1dca24b29ac9925e1303dfacb/Untitled.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Ce3nZm5j-1685532776854)(%E5%8D%95%E8%B0%83%E9%98%9F%E5%88%97%E4%BC%98%E5%8C%96dp%20dd9f82e1dca24b29ac9925e1303dfacb/Untitled%201.png)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cDlxFfpM-1685532776855)(%E5%8D%95%E8%B0%83%E9%98%9F%E5%88%97%E4%BC%98%E5%8C%96dp%20dd9f82e1dca24b29ac9925e1303dfacb/Untitled%202.png)]
烽火传递 题目大意有n个烽火台在连续的k个烽火台中至少要有一个发出信号烽火台发出信号需要消耗代价问你要使得满足对于所有的烽火台满足条件最小的代价是多少。 例如烽火台及其代价如下所示
1 2 5 6 2 其中k3
我们必须选择两个
1 和 5代价为61 和 6代价为7……2 和 2代价为4可以得知这是最优解。
因此我们定义 d p [ i ] dp[i] dp[i] 数组 表示当前位置的最小代价值因此最后的结果就是 d p [ n ] dp[n] dp[n]
其中状态转移可以由前一些位置的最小的值来转移得到 d p [ i ] m i n ( d p [ j ] ) w [ i ] dp[i]min(dp[j])w[i] dp[i]min(dp[j])w[i]
其中 d p [ j ] dp[j] dp[j] 中的 j 的位置我们可以根据 k k k 的值来确定 j ∈ [ i − k , i − 1 ] j \in \left [i-k,i-1 \right ] j∈[i−k,i−1]
这意味如果我们点燃位置为 i i i 的烽火台则必须满足在 [ i − k , i − 1 ] \left [i-k,i-1 \right ] [i−k,i−1] 位置至少点燃一个烽火台
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EiRqpji2-1685532776855)(%E5%8D%95%E8%B0%83%E9%98%9F%E5%88%97%E4%BC%98%E5%8C%96dp%20dd9f82e1dca24b29ac9925e1303dfacb/Untitled%203.png)]
因此我们枚举 i i i 的位置对于每一个位置通过单调队列维护前面区间内一个最小值然后根据上面的状态转移方程转移即可。 本题的单调队列的滑动窗口范围是往右滑动的 #includebits/stdc.h
#if 0#define int long long
#endifconst int N1e610;
int n,k;
int w[N],dp[N];
std::dequeint deq;
signed main(){ std::cinnk;for (int i1;in;i){std::cinw[i];} int ans1e9;for (int i1;in;i){if (!deq.empty() deq.front()i-k){deq.pop_front();}//维护队列最小值while (!deq.empty() dp[i-1]dp[deq.back()]){deq.pop_back();}deq.push_back(i-1);dp[i]dp[deq.front()]w[i];if (in-k1){ansstd::min(ans,dp[i]);}}std::coutans;return 0;
}修剪草坪 题目大意在数列中选出长度不超过k的子序列然后得到每个子序列的和计算和的最大值其中元素不能重复选择。 示例给出了
1 2 3 4 5 其中k2
最优解是选择1 2 和 4 5两个子序列结果为 12
根据贪心的思想如果我们想要使得最后的和最大 应该尽量往长了选则我们假设选择了n个长度为 k 的子序列则第 k1 个数字一定不会选因此我们就可以对这个不会选的数字进行操作。
与其让我们求n个 长度为k 的子序列的和的最大值不如求在 n个 长度为k1 的子序列中选择最小值然后计算他们的和最后直接用整个数列的和减去由若干最小值组成的和即可。
因此状态转移方程如下 d p [ i ] m i n ( d p [ j ] ) w [ i ] dp[i]min(dp[j]) w[i] dp[i]min(dp[j])w[i]
注意 d p dp dp 数组表示的是在 k1 长度中选择的最小值。
其中 j j j 的取值范围是 j ∈ [ i − k , i − 1 ] j \in \left [i-k,i-1 \right ] j∈[i−k,i−1] 本题的单调队列的滑动窗口范围是往右滑动的 #includebits/stdc.h
#if 1#define int long long
#endifconst int N1e610;
int n,k;
int w[N],dp[N];
std::dequeint deq;
signed main(){ std::cinnk;for (int i1;in;i){std::cinw[i];} k1;//选择子序列并且使得数列中没有连续的超过k个数被选使得选择的数之和最大//选择不超过连续k个数字之和的最大值 sum-选择k1个数字组成若干个最小值int sum1e18;for (int i1;in;i){if (!deq.empty() deq.front()i-k){deq.pop_front();}while (!deq.empty() dp[deq.back()]dp[i-1]){deq.pop_back();}deq.push_back(i-1);dp[i]dp[deq.front()]w[i];if (in-k1){//获得最小值sumstd::min(sum,dp[i]);}}std::coutstd::accumulate(w1,w1n,0ll)-sum;return 0;
}绿色通道
绿色通道 - 洛谷 题目大意在规定的时间内做一定数量的题目做一道题目需要消耗一定的时间。最后使得未做的最长的空题目段的长度最小值求这个最小值。 根据题目描述的最大值最小我们很容易想到是二分答案
同时题目告诉你了最长的空题目段越长马老师越生气这就是相当于满足了单调性。
因此我们可以二分查找 空题目段的长度然后选择套用二分查找求最小值的模板即可。
其中我们在二分查找的过程中假设当前的空题目段长度为 k 则第 k1 题目一定不是因此我们就可以像上一道题目那样单调队列维护区间最小值。
注意到我们二分的是 k1 的长度因此最后我们还需要 -1
#includebits/stdc.h
#if 1#define int long long
#endifconst int N5e410;
int dp[N],w[N];
int n,t;
bool check(int mid){//mid表示选择的空题目段长1 std::dequeint deq;memset(dp,0,sizeof(dp));for (int i1;in;i){if (!deq.empty() deq.front()i-mid){deq.pop_front();}while (!deq.empty() dp[deq.back()]dp[i-1]){deq.pop_back();}deq.push_back(i-1);dp[i]dp[deq.front()]w[i];if (in-mid1 dp[i]t){//mid越大表示选择的空题目段越长则能做的题目就越少因此不超过t分钟的条件就越容易满足此时返回true更新最小值return true;}}return false;
}
signed main(){std::cinnt;for (int i1;in;i){std::cinw[i];}//最大值最小使得最长的空题段最短是多少//二分选择的 空题段长1int l-1,rn1;while (l1r){int midlr1;if (check(mid)){rmid;}else{lmid;}}std::coutr-1;return 0;
}琪露诺
琪露诺 - 洛谷 题目大意每次可以走 [ x L , x R ] \left [xL,xR \right ] [xL,xR] 中的任意一个位置同时每个位置具有一个值最后使得走完这 n 个点之后 能够获得的最大值是多少。 很容易可以看出来这道题目是给定区间的单调队列优化 的问题。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8gykVs2O-1685532776856)(%E5%8D%95%E8%B0%83%E9%98%9F%E5%88%97%E4%BC%98%E5%8C%96dp%20dd9f82e1dca24b29ac9925e1303dfacb/Untitled%204.png)]
状态转移方程与前面都是一样的。
#includebits/stdc.h
#if 0#define int long long
#endif
const int N2e510;
int n,l,r;
int w[N],dp[N];
std::dequeint deq;
signed main(){std::cinnlr;for (int i0;in1;i){std::cinw[i];}//i可以跳跃到[il,ir]中的任意位置//同理i位置可以由[i-r,i-l]区间中任意位置跳跃过来维护窗口中的最大值即可memset(dp,-0x3f,sizeof(dp));dp[0]0;int ans-1e9;//注意从l开始因为一开始只能跳到[l,r]的位置for (int il;in;i){if (!deq.empty() deq.front()i-r){deq.pop_front();}//维护单调队列最大值while (!deq.empty() dp[deq.back()]dp[i-l]){deq.pop_back();}deq.push_back(i-l);dp[i]dp[deq.front()]w[i];if (in-r1){ansstd::max(ans,dp[i]); //在最后的区间内累加答案}}std::coutans;return 0;
}旅行问题 题目大意n个车站组成一个环在每个车站有加油量和到下一站的距离问你从任意的车站出发能够到达最后的终点即绕一圈。 我们定义 s u m [ i ] sum[i] sum[i] 表示为从 i 号车站出发到下一站剩余的流量 s u m [ i ] s u m [ i n ] o i l [ i ] − d i s [ i ] sum[i] sum[in] oil[i] -dis[i] sum[i]sum[in]oil[i]−dis[i]
对于环形的问题我们常常断环成链。
然后计算他们的前缀和 s u m [ i ] s u m [ i − 1 ] sum[i] sum[i-1] sum[i]sum[i−1]
对于判断 i 号点能否绕一圈我们可以用 s u m [ j ] − s u m [ i − 1 ] 0 sum[j]-sum[i-1]0 sum[j]−sum[i−1]0
来判断如果此值大于等于0则说明 i 号点可以绕一圈对于 j 我们可以单调队列维护一个最小的 j
同时判断逆时针能够绕一圈我们可以维护一个后缀和然后执行相反的操作即可 s u m [ j ] − s u m [ i 1 ] 0 sum[j]-sum[i1]0 sum[j]−sum[i1]0 此题我们需要同时维护往左滑动的窗口代表顺时针和一个维护往右滑动的窗口代表逆时针。 #includebits/stdc.h
#if 1#define int long long
#endifconst int N1e610;
int n;
int oil[N],dis[N];
int sum[N2],fg[N2]; //sum[i]表示从i点出发顺时针或者逆时针到达各个点的剩余油量
std::dequeint deq;
signed main(){std::cinn;for (int i1;in;i){std::cinoil[i]dis[i];}//顺时针for (int i1;in;i){sum[i]sum[in]oil[i]-dis[i];}for (int i1;in*2;i){sum[i]sum[i-1];}//窗口往左滑动for (int in*2;i1;i--){if (!deq.empty() deq.front()in-1){deq.pop_front();}//维护最小的sum[j],如果sum[j]-sum[i-1]0则满足i点可以绕一圈while (!deq.empty() sum[deq.back()]sum[i]){deq.pop_back();}deq.push_back(i);if (in sum[deq.front()]-sum[i-1]0){fg[i]true;}}memset(sum,0,sizeof(sum));deq.clear();//逆时针dis[0]dis[n];for (int in;i1;i--){sum[i]sum[in]oil[i]-dis[i-1];}for (int in*2;i1;i--){sum[i]sum[i1];}//窗口往右边滑动for (int i1;in*2;i){if (!deq.empty() deq.front()i-n1){deq.pop_front();}while (!deq.empty() sum[deq.back()]sum[i]){deq.pop_back();}deq.push_back(i);if (in1 sum[deq.front()]-sum[i1]0){//注意此时的序号为i-nfg[i-n]true;}}for (int i1;in;i){if (fg[i]){std::coutTAK\n;}else{std::coutNIE\n;}}return 0;
}Watching Fireworks is Fun
Watching Fireworks is Fun - 洛谷 题目大意通过移动位置x使得 b i − ∣ a i − x ∣ b_i - |a_i-x| bi−∣ai−x∣ 来获得最大值 注意到从一个位置到另一个位置可以通过两种方式得到
窗口向右滑动
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zvmx4IpO-1685532776856)(%E5%8D%95%E8%B0%83%E9%98%9F%E5%88%97%E4%BC%98%E5%8C%96dp%20dd9f82e1dca24b29ac9925e1303dfacb/Untitled%205.png)]
窗口向左滑动
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eeg75d6t-1685532776857)(%E5%8D%95%E8%B0%83%E9%98%9F%E5%88%97%E4%BC%98%E5%8C%96dp%20dd9f82e1dca24b29ac9925e1303dfacb/Untitled%206.png)]
我们定义 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示当前放的是第 i 次烟花位置为 j 时的最大权值。
状态转移方程如下 d p [ n o w ] [ i ] d p [ p r e ] [ j ] b [ i ] − a b s ( a [ i ] − x ) dp[now][i]dp[pre][j] b[i]-abs(a[i]-x) dp[now][i]dp[pre][j]b[i]−abs(a[i]−x)
可以利用滚动数组优化把数组将为二维。
#includebits/stdc.h
#if 1#define int long long
#endifconst int N150010;
int dp[2][N]; //滚动数组: dp[i][j]表示放第i个烟花当前位置位于j时的最大快乐值
int n,m,d;
int a[N],b[N],t[N];
signed main(){std::cinnmd;for (int i1;im;i){std::cina[i]b[i]t[i];}memset(dp,-0x3f,sizeof(dp));for (int i1;in;i){dp[0][i]0; //初始化放第0个烟花位置在任何时刻都是0快乐度}//遍历烟花for (int z1;zm;z){//now表示当前pre表示上一个int nowz1,pre(z-1)1;std::dequeint deq;//遍历位置窗口往右滑动for (int i1;in;i){if (!deq.empty() deq.front()i-d*(t[z]-t[z-1])){deq.pop_front();}//维护队列最大值while (!deq.empty() dp[pre][deq.back()]dp[pre][i]){deq.pop_back();}deq.push_back(i);dp[now][i]dp[pre][deq.front()]b[z]-abs(a[z]-i);}//窗口往左滑动for (int in;i1;i--){if (!deq.empty() deq.front()id*(t[z]-t[z-1])){deq.pop_front();}while (!deq.empty() dp[pre][deq.back()]dp[pre][i]){deq.pop_back();}deq.push_back(i);dp[now][i]std::max(dp[now][i],dp[pre][deq.front()]b[z]-abs(a[z]-i));}}int ans-1e18;//最后一次在m1位置为j时枚举一个最大值for (int i1;in;i){ansstd::max(dp[m1][i],ans);}std::coutans;return 0;
} 瑰丽华尔兹
[NOI2005] 瑰丽华尔兹 - 洛谷 题目大意往上下左右四个方向移动每次都可以选择移动或者停止求最后的最大移动路程 设 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示当前位置为 ( i , j ) (i,j) (i,j) 时的最大移动距离。
我们首先需要枚举四个方向然后进行求解。
我们先来看往右移动的话
很容易想到状态转移方程 d p [ i ] [ j ] m a x ( d p [ i ] [ k ] j − k ) dp[i][j]max(dp[i][k]j-k) dp[i][j]max(dp[i][k]j−k)
即当前点的最大移动距离就等于 ( i , k ) (i,k) (i,k) 点的距离 ( j − k ) (j-k ) (j−k) 的距离。
因此我们只需要维护一个 d p [ i ] [ k ] j − k dp[i][k] j-k dp[i][k]j−k 的最大值我们可以使用单调队列进行维护。
这是向右移动的情况再考虑其他三种情况也是同样的道理。
但是发现一个问题往右移动 i 是不变的但是往下移动的时候j 又是不变的我们很难用 d p [ i ] [ k ] dp[i][k] dp[i][k] 来具体的表示四个方向因此我们抽象为 d p [ i ] [ j ] m a x ( f j − p o s ) dp[i][j]max(fj-pos) dp[i][j]max(fj−pos)
其中 f f f 就是转移之前的最大移动距离 p o s pos pos 表示的就是转移之前的那个位置。
因此我们对于四种方向的枚举就可以实现了
for (int i1;ik;i){int s,t,d; //时间区间[s,t] d方向 1234 上下左右std::cinstd; int timet-s1;if (d1){//上for (int i1;im;i){get(n,i,n,time,d);}}if (d2){//下for (int i1;im;i){get(1,i,n,time,d);}}if (d3){//左for (int i1;in;i){get(i,m,m,time,d);}}if (d4){//右for (int i1;in;i){get(i,1,m,time,d);}}}其中 g e t get get 函数就是我们维护单个方向滑动窗口最大值的函数
x和y每个方向的起始位置L表示最多在这个方向移动L距离time表示时间间隔。d表示方向用于移动。
void get(int x,int y,int L,int time,int d);我们在此函数中利用滑动窗口维护一个最大值即可注意当碰到障碍的时候我们的窗口清零。
#includebits/stdc.h
#if 0#define int long long
#endifconst int N210;
int n,m,x,y,k,ans;
char map[N][N];
int dp[N][N]; //dp[i][j]表示在(i,j)位置的最大价值
int dx[5]{0,-1,1,0,0},dy[5]{0,0,0,-1,1};
struct Node{int pos,dp; //位置和最长距离
};
void get(int x,int y,int L,int time,int d){//(x,y)表示起始位置L表示当前方向最长移动长度time表示时间长度std::dequeNode deq;//注意!!! 这个地方要从(x,y)开始所有一开始不能把x,y放在下面因此要放在for循环的后面for (int i1;iL;i,xdx[d],ydy[d]){ //朝着方向d一直移动if (map[x][y]x){deq.clear();}else{//单调队列维护最大值if (!deq.empty() deq.front().posi-time){deq.pop_front();}//维护窗口最大值while (!deq.empty() deq.back().dpi-deq.back().posdp[x][y]){deq.pop_back();}deq.push_back({i,dp[x][y]});dp[x][y]deq.front().dpi-deq.front().pos;ansstd::max(ans,dp[x][y]);}}
}
signed main(){std::cinnmxyk;for (int i1;in;i){for (int j1;jm;j){std::cinmap[i][j];}}memset(dp,-0x3f,sizeof(dp));dp[x][y]0;for (int i1;ik;i){int s,t,d; //时间区间[s,t] d方向 1234 上下左右std::cinstd; int timet-s1;if (d1){//上for (int i1;im;i){get(n,i,n,time,d);}}if (d2){//下for (int i1;im;i){get(1,i,n,time,d);}}if (d3){//左for (int i1;in;i){get(i,m,m,time,d);}}if (d4){//右for (int i1;in;i){get(i,1,m,time,d);}}}std::coutans;return 0;
}股票交易
[SCOI2010]股票交易 - 洛谷 题目大意在某天可以选择买入股票卖出股票其中买入和卖出都有数量限制并且也具有最大持股数限制并且还具有时间间隔限制求得最后能获得的最大利润。 定义 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示第 i i i 天持股 j j j 数量的最大利润。
我们可以分成四种情况讨论
只买入 d p [ i ] [ j ] − a s ⋅ j dp[i][j]-as\cdot j dp[i][j]−as⋅j不买不卖 d p [ i ] [ j ] m a x ( d p [ i ] [ j ] , d p [ i − 1 ] [ j ] ) dp[i][j]max(dp[i][j],dp[i-1][j]) dp[i][j]max(dp[i][j],dp[i−1][j])在之前某天的基础上买入 d p [ i ] [ j ] m a x ( d p [ i − w − 1 ] [ k ] − a p ∗ ( j − k ) ) dp[i][j]max(dp[i-w-1][k]-ap*(j-k)) dp[i][j]max(dp[i−w−1][k]−ap∗(j−k)) 其中 k k k 的取值范围 k ∈ [ j − a s , j ] k\in [j-as,j] k∈[j−as,j] 表示全买或者一个都不买 在之前某天的基础上卖出 d p [ i ] [ j ] m a x ( d p [ i − w − 1 ] [ k ] b p ∗ ( k − j ) ) dp[i][j]max(dp[i-w-1][k]bp*(k-j)) dp[i][j]max(dp[i−w−1][k]bp∗(k−j)) 其中 k k k 的取值范围 k ∈ [ j , j b s ] k \in [j,jbs] k∈[j,jbs] 表示一个都不卖或者全卖
因此我们便可以使用单调队列维护窗口的最大值了。
其中 k k k 便是我们需要维护的值。
注意窗口的移动情况
买入窗口往右滑顺序遍历卖出窗口往左滑逆序遍历
#includebits/stdc.h
#if 0#define int long long
#endifconst int N5e310;
int t,maxp,w;
int ap,bp,as,bs;
int dp[N][N]; //dp[i][j]表示第i天持股j时的最大价值
signed main(){memset(dp,-0x3f,sizeof(dp));std::cintmaxpw; //t天持股不能超过maxp交易间隔w天for (int i1;it;i){//买入价ap卖出价bp最多买入as最多卖出bsstd::cinapbpasbs; //凭空买入for (int j0;jas;j){dp[i][j]-ap*j;}//不买不卖for (int j0;jmaxp;j){dp[i][j]std::max(dp[i][j],dp[i-1][j]);}if (iw){continue;}//买入std::dequeint deq;for (int j0;jmaxp;j){if (!deq.empty() deq.front()j-as){deq.pop_front();}while (!deq.empty() dp[i-w-1][deq.back()]deq.back()*ap-j*apdp[i-w-1][j]){deq.pop_back();} deq.push_back(j);dp[i][j]std::max(dp[i][j],dp[i-w-1][deq.front()]-ap*(j-deq.front()));}deq.clear();//卖出for (int jmaxp;j0;j--){if (!deq.empty() deq.front()jbs){deq.pop_front();}while (!deq.empty() dp[i-w-1][deq.back()]deq.back()*bp-j*bpdp[i-w-1][j]){deq.pop_back();}deq.push_back(j);dp[i][j]std::max(dp[i][j],dp[i-w-1][deq.front()]bp*(deq.front()-j));}}std::coutdp[t][0];return 0;
}
