题解 P3800 【Power收集】

先无良宣传一下博客 $wwwwww$ [文章列表 - 核融合炉心 - 洛谷博客](https://www.luogu.org/blog/koishikoishi/) ------------ ## 知识点 : $DP$ 优化 , 单调队列 - ### 题意: 有一个 $(N\times M)$ 大小的矩阵 部分矩阵中的点 **带有价值** 可以选择第一行 , 任何一个位置作为起点 . 对于当前的位置 $(i,j)\ $ (表示在第 $i$ 行第 $j$ 列) 可以转移到: $(i+1,\ [j-T , j+T]\ )$ 中任意一个点 $(j-T>0\ ,\ j+t\leqslant M)$ 并且获得当前所在点的价值 . **求** : 可以取得的 最大价值和 样例解释:  1.灵梦从 $(1,1)$出发 : 总价值$+3$ , 现在为 $3$ 2.灵梦转移到 $(2,2)$ : 总价值$+3$ ,现在为 $6$ 3.灵梦转移到 $(3,3)$ : 总价值$+3$ ,现在为 $9$ 故 , 总价值为 $9$ ------------ - ### 分析题意: 很显然 这是一道 $DP$ 状态转移方程 极其简单 : 用 $f[i][j]$ 表示在点 $(i,j)$ 能到达的最大价值和 , 则有: $f[i][j] = max(f[i-1][k]) + v[i][j]\ ,\ (k\in [j-T , j+T]\ )$ - 暴力: 直接枚举所有点 , 再枚举能转移到他的点 ? 复杂度 $O(N^3)$ 级别 , $40Pts$ 到手 考虑优化 : - 可知: 第 $i$ 行上点的 $f[][]$ , 只与第 $i-1$ 行有关 则可将每相邻的两行 , 单独拆分出来考虑 : 如图:  可以发现 : 1. 转移到 点$(i,j)$ 的点 , 为 $i-1$ 行 , 区间 $\underline{[j-T,j+T]}$ 中 , $f[][]$ 最大的点 2. 转移到 点$(i,j+1)$ 的点 , 为 $i-1$ 行 ,区间 $\underline{[j-T+1,j+T+1]}$ 中 , $f[][]$ 最大的点 3. 转移到 点$(i,j+2)$ 的点 , 为 $i-1$ 行 ,区间 $\underline{[j-T+2,j+T+2]}$ 中 , $f[][]$ 最大的点 后两个区间 , 都可以通过 上一个区间 **右移一个单位** 得到 这不禁让我们想到了另一道题 : [P1886 滑动窗口](https://www.luogu.org/problemnew/show/P1886) 如果您还未学习过单调队列 , 推荐这篇文章: [【洛谷日报#9】 [Sweetlemon] 朝花中学OI队的奋斗历程——浅谈单调队列](https://sweetlemon.blog.luogu.org/dan-diao-dui-lie) 这种 **滑动窗口型** 最值问题 , 显然 , 可以通过 单调队列 来进行维护 . 由上 , 我们便找到了一种合适 $DP$ 优化方法: 单调队列优化. ------------ - ### 算法实现: 假设,现在已经更新到第 $i$ 行 : 1. 先初始化单调队列 , 将能够更新 $(i,1)$ 的点$(i,k) , (k \in [1,1+T])$ , 加入单调队列 2. 开始循环 , 更新 $[1,M]$ 中每一个点 : - 将能够转移到 $j$ 的最右侧一个点 $(i-1 , j+T)$ , 加入队列 - 使用单调队列找到能够转移到 $j$ 的点的最大$f[][]$ - 用最大的$f[][]$ 更新 $f[i][j]$ 3. **清空单调队列** , 外层循环进入下一层 ,更新第 $i+1$ 行 最后找到最后一行中 , 最大的 $f[N][j]$ , 即所求最值 . ------------ 上代码: 由于使用了手写数组模拟队列 , 清空时只需重置头尾指针 , 及队首元素即可 . 常数吊打 $deque$ ```cpp #include<cstdio> #include<ctype.h> #include<cstring> #define int long long #define max(a,b) a>b?a:b //===================================== const int MARX = 4e3+10; int n,m,k,t, now,ans; int f[MARX][MARX]; int head=1,tail=1;//手写双端队列 int q[MARX]={9223372036854775807};//为q[0]赋一个极大值,来防止插入元素时越界 //===================================== inline int read() { int fl=1,w=0;char ch=getchar(); while(!isdigit(ch) && ch!='-') ch=getchar(); if(ch=='-') fl=-1; while(isdigit(ch)){w=w*10+ch-'0',ch=getchar();} return fl*w; } void in(int x)//向单调队列中插入元素 { while(f[now-1][x]>f[now-1][q[tail]] && tail>=head) tail--;//取出队尾小于插入元素的数 , 以保证单调性 q[++tail]=x;//插入队尾 } int find(int x)//查询元素 { if(x+t<=m)in(x+t);//将能转移到x点 的 最后一个元素 x+t 插入队列 while(q[head]+t<x) head++;//找到队首第一个能够转移到x的点 return q[head]; } //===================================== signed main() { n=read(),m=read(),k=read(),t=read(); while(k--) { int x=read(),y=read(),w=read(); f[x][y]=w; } for(now=2;now<=n;now++)//从第二行,开始转移 { for(int i=1;i<=t;i++) in(i);//初始化单调队列 , 满足能够 转移j=1的点 for(int j=1;j<=m;j++) f[now][j]+=f[now-1][find(j)];// 进行转移 head=tail=1 , q[1]=0;//清空队列 } for(int i=1;i<=m;i++)//取得最大值 ans=max(ans,f[n][i]); printf("%lld",ans); } ``` ------------ 完成了这篇题解 , 东方众信仰 $++$