题解 P3800 【Power收集】
囧仙
2020-04-11 23:59:34
东方Project相关试题（Easy-Normal） [3 / 30]
- 题目大意
给出一个 $n \times m$ 的棋盘，有一些格子上面有权值。一开始站在第一行，每次下移一行，可以向两边走 $t$ 步以内，求权值和最大的路径
- 解法
这题和 dp 经典入门题，P1216 十分相似，只是每次行走的方案多了很多
所以很容易就可以想到，设 $dp_{i,j}$ 表示走到第 $i$ 行，第 $j$ 列的最大权值和，每次的转移是：
$$dp_{i,j} = max(dp_{i - 1,k}) + c_{i,j}(j - t \le k \le j + t)$$
如果你暴力去枚举的话，是 $O(nmt)$ 的，显然不能通过
但是我们枚举的区间实际上是很有规律的，它的长度相同，并且每次只会在左边少一个数，右边多一个数
显然，这个是单调队列的经典例题，滑动窗口
所以每次用单调队列去维护最大值就可以了，时间复杂度 $O(nm)$
代码：
```cpp
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,k,t;
int c[4005][4005];
int dp[4005][4005];
int h = 1,r = 1;
struct node{
int id,val;
}que[4005];
void pop(int id){
while(h != r){
if(que[h].id < id){
h++;
}else{
return;
}
}
}
void push(int id,int val){
while(h != r){
if(que[r - 1].val <= val){
r--;
}else{
break;
}
}
que[r++] = {id,val};
}
int main(){
scanf("%d%d%d%d",&n,&m,&k,&t);
for(int i = 1;i <= k;i++){
int x,y,val;
scanf("%d%d%d",&x,&y,&val);
c[x][y] += val;
}
for(int i = 1;i <= n;i++){
h = r = 1;
for(int j = 1;j <= t;j++){
push(j,dp[i - 1][j]);
}
for(int j = 1;j <= m;j++){
pop(j - t);
if(j + t <= m) push(j + t,dp[i - 1][j + t]);
dp[i][j] = que[h].val + c[i][j];
}
}
int ans = 0;
for(int j = 1;j <= m;j++){
ans = max(ans,dp[n][j]);
}
printf("%d\n",ans);
return 0;
}
```