前言
历尽千辛万苦，终于在自己和老师的帮助下把P3800 Power 收集给过了，有一些trick要讲
P3800 Power
题目背景
据说在红雾异变时，博丽灵梦单身前往红魔馆，用十分强硬的手段将事件解决了。
然而当时灵梦在 Power 达到 MAX 之前，不具有“上线收点”的能力，所以她想要知道她能收集多少 P 点，然而这个问题她答不上来，于是她找到了学 OI 的你。
题目描述
可以把游戏界面理解成一个 \(N\) 行 \(M\) 列的棋盘，有 \(K\) 个格子上有 P 点，其价值为 \(\operatorname{val}(i,j)\)。
初始灵梦可以选择在第一行的任意一个格子出发，每秒她必须下移一格。
灵梦具有一个左右移动的速度 \(T\)，可以使她每秒向左或右移动至多 \(T\) 格，也可以不移动，并且在单次移动中不能折返。移动可视为瞬间完成，不经过路途上的点，只能获得目标格子的 P 点。
求最终她能获得的所有 P 点的价值总和最大是多少？
输入格式
第一行四个整数，\(N,M,K,T\)。
接下来 \(K\) 行每行 \(3\) 个整数 \(x,y,v\)，代表第 \(x\) 行第 \(y\) 列有一个 \(\operatorname{val}\) 为 \(v\) 的 P 点，数据保证一个格子上最多只有 \(1\) 个 P 点。
输出格式
一个整数，表示灵梦能获得的 P 点的价值总和的最大值。
输入输出样例 #1
输入 #1
3 3 4 1
1 1 3
1 2 1
2 2 3
3 3 3
输出 #1
9
说明/提示
对于 \(40\%\) 的测试点，\(1 \le N,M,T,K \le 200\)。
对于 \(100\%\) 的测试点，\(1 \le N,M,T,K \le 4000\)，\(0 \le v \le 100\)，\(N,M,K,T\) 均为整数。
by-szc
思路
转移方程
注意到题目支持\(O(mn)\)做法，以及移动区间的长度不变，且对于每一行的第i个值都是有上一行的\([i-t,i+t]\)区间的最大值转移过来的，类似滑动窗口，想到单调队列优化dp
可优化部分\(max(dp[i-1][j-t],dp[i-1][j-t+1],...,dp[i-1][j+t])\)
AC代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=4005;
int a[N][N];
int dp[N][N];
int main(){int n,m,k,t;cin>>n>>m>>k>>t;for(int i=1;i<=k;i++){int x,y,w;cin>>x>>y>>w;a[x][y]=w;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){dp[i][j]=-1e9;} }for(int i=1;i<=m;i++){dp[0][i]=0;}for(int i=1;i<=n;i++){int q[N];int l=1,r=0;int nxt=1;//维护下一个要选的点for(int j=1;j<=m;j++){int rim=min(m,j+t);//为了不让单调队列的右端点出界while(l<=r&&q[l]<j-t) l++;while(nxt<=rim){//没出界的点就选int pos=nxt;while(l<=r&&dp[i-1][q[r]]<=dp[i-1][pos]) r--;q[++r]=pos;nxt++;}if(l<=r) dp[i][j]=dp[i-1][q[l]]+a[i][j];}}int ans=0;for(int i=1;i<=m;i++){ans=max(ans,dp[n][i]);}cout<<ans;return 0;
}
总结重要！
继上一个题解P1725 琪露诺总结的要处理左端点可能出界的情况
而这一篇要处理右端点可能出界的情况集齐龙珠
预防左端点出界处理方法
for(int i=L;i<=n;i++){//令i=Lwhile(l<=r&&q[l]+R<i) l++;while(l<=r&&dp[q[r]]<=dp[i-L]) r--;//因为要是这里的i-L>=0所以上两行的i要从L开始q[++r]=i-L;dp[i]=dp[q[l]]+a[i];if(i+R>n){ans=max(ans,dp[i]);}}
预防右端点出界处理方法
int q[N];
int l=1,r=0;
int nxt=1;//维护下一个要选的点
for(int j=1;j<=m;j++){int rim=min(m,j+t);//为了不让单调队列的右端点出界while(l<=r&&q[l]<j-t) l++;while(nxt<=rim){//没出界的点就选int pos=nxt;while(l<=r&&dp[i-1][q[r]]<=dp[i-1][pos]) r--;q[++r]=pos;nxt++;}if(l<=r) dp[i][j]=dp[i-1][q[l]]+a[i][j];
}
剩下交给刷题吧