AC日记——Power收集 洛谷 P3800

Power收集

思路：

　　单调队列优化dp；

代码：

#include <bits/stdc++.h>
using namespace std;
#define maxn 4005
struct QueueType {
    int p,dis;
};
struct QueueType que[maxn];
int dp[maxn],Map[maxn][maxn],n,m,k,t,temp[maxn];
inline void in(int &now)
{
    char Cget=getchar();now=0;
    while(Cget>'9'||Cget<'0')Cget=getchar();
    while(Cget>='0'&&Cget<='9')
    {
        now=now*10+Cget-'0';
        Cget=getchar();
    }
}
int main()
{
    in(n),in(m),in(k),in(t);int x,y,di;
    while(k--) in(x),in(y),in(di),Map[x][y]=di;
    for(int i=1;i<=n;i++)
    {
        int h=0,tail=-1,num=0;
        for(int v=1;v<=m;v++)
        {
            int l=max(1,v-t),r=min(m,v+t);
            while(num<r)
            {
                num++;
                while(tail>=h&&dp[num]>que[tail].dis) tail--;
                que[++tail].p=num,que[tail].dis=dp[num];
            }
            while(h<=tail&&que[h].p<l) h++;
            dp[v]=que[h].dis+Map[i][v];
        }
    }
    int ans=0;
    for(int i=1;i<=m;i++) ans=max(dp[i],ans);
    cout<<ans;
    return 0;
}