传送门
解题思路
很显然的一个线性dp,设dp[i][j]为到第i行第j列的最大power。
可以从前一行dp[i-1][j-t]~dp[i-1][j+t]转移过来。
用单调队列优化一下即可。
防止MLE可以用滚动数组优化,然后k个P点用二维map存一下。
注意:
不能直接
dp[j][now^1]=dp[q.front()][now]+ma[i][j]
因为ma[i][j]如果没有会自动开一个空间(i,j)并赋初值0。
正确操作应该是
dp[j][now^1]=dp[q.front()][now];
if(ma[i].find(j)!=ma[i].end()) dp[j][now^1]+=ma[i][j];
AC代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
map<int,map<int,int> > ma;
int n,m,k,t,ans=-1e9,dp[4005][2],now;
int main(){
ios::sync_with_stdio(false);
cin>>n>>m>>k>>t;
for(int i=1;i<=k;i++){
int x,y,v;
cin>>x>>y>>v;
ma[x][y]=v;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) dp[j][now^1]=0;
deque<int> q;
for(int j=1;j<=t;j++) {
while(!q.empty()&&dp[j][now]>dp[q.back()][now]) q.pop_back();
q.push_back(j);
}
for(int j=1;j<=m;j++){
if(!q.empty()&&j-q.front()>t) q.pop_front();
while(!q.empty()&&j+t<=m&&dp[j+t][now]>dp[q.back()][now]) q.pop_back();
if(j+t<=m) q.push_back(j+t);
dp[j][now^1]=dp[q.front()][now];
if(ma[i].find(j)!=ma[i].end()) dp[j][now^1]+=ma[i][j];
if(i==n) ans=max(ans,dp[j][now^1]);
}
now^=1;
}
cout<<ans;
return 0;
}