P3800 Power收集

传送门

DP
每次向下一格，显然是DP
方程也十分显然：
设$f[i][j]$为到第$i$行第$j$列时能得到的最大价值
显然$f[i][j]=max(f[i-1][k]+v[i][j]),（ max(0,j-t)<=k<=min(m,j+t) ）$
然后40分，其他超时..
考虑优化
方程稍微变一下：$f[i][j]=max(f[i-1][k])+v[i][j],$
同样$max(0,j-t)<=k<=min(m,j+t)$;
发现只要能快速处理出$f[i-1][k]$的最大值就能快速更新$f[i][j]$
因为区间大小不会改变（不考虑达到边界），改变的只有区间的开端，所以可以考虑通过单调队列预处理..
然后就结束了，稍微注意边界问题就好了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n,m,k,t;
int map[4005][4005],f[4005][4005];
int q[4005],ans[10005];
int main()
{
    int a,b,c;
    cin>>n>>m>>k>>t;
    int s=t*2+1;
    while(k--)
    {
        scanf("%d%d%d",&a,&b,&c);
        map[a][b]=c;
    }
    //cout<<endl;
    for(int i=1;i<=n;i++)
    {
        int head=1,last=0;
        //单调队列预处理
        for(int j=1;j<=m+t;j++)//注意j到m+t
        {
            while(head<=last&&f[i-1][j]>=f[i-1][q[last]])
                last--;
            while(head<=last&&j-q[head]>=s)
                head++;
            q[++last]=j;
            ans[j]=f[i-1][q[head]];
            //cout<<ans[j]<<" ";
        }
        for(int j=1;j<=m;j++)
            f[i][j]=ans[j+t]+map[i][j];
        //cout<<endl;
    }
    int Ans=0;
    for(int i=1;i<=m;i++)
        Ans=max(Ans,f[n][i]);
    cout<<Ans;
    return 0;
}