题解：P3800 Power收集

· · 题解

一眼 DP，设 f_{i,j} 表示走到坐标 (i,j) 的最大 POWER 值，那么有：

f_{i,j} = a_{i,j} + \max_{p=j-t}^{j+t} f_{i-1,p}

即每次从上一行可行的位置向下转移（a_{i,j} 表示该点上的原始 POWER 值）。

直接计算的时间复杂度 O(nm^2)，无法通过。

观察上式所求 \max_{p=j-t}^{j+t} f_{i-1,p} 部分，是一个裸的静态 RMQ 模板，自然可以想到用好写而常数小的 ST 表处理。

对于每一行，对其上一行建 ST 表。更新坐标 (i,j) 时，在区间 [j-t,j+t] 内查询最大值进行累加就能直接得到答案。（注意防越界）

时间复杂度 O(n m \log m)，可过。

代码：

#include<cstdio>
#include<algorithm>
using namespace std;

const int N=4005;
int n,m,k,t;
int st[N][15],f[N][N];

int main()
{
    scanf("%d%d%d%d",&n,&m,&k,&t);
    for(int i=1;i<=k;i++)
    {
        int x,y,v;
        scanf("%d%d%d",&x,&y,&v);
        f[x][y]=v;
    }
    int tp=__lg(m),ans=0; //__lg()函数用于计算以2为底的对数
    for(int i=2;i<=n;i++) //从第二行开始计算，因为第一行可以从任意位置开始
    {
        for(int j=1;j<=m;j++)
            st[j][0]=f[i-1][j];
        for(int l=1;l<=tp;l++) //建立ST表
            for(int x=1;x+(1<<l)-1<=m;x++)
                st[x][l]=max(st[x][l-1],st[x+(1<<(l-1))][l-1]);
        for(int j=1;j<=m;j++)
        {
            auto query = [&](int l,int r) -> int //lambda函数写法，可以直接当正常函数用
            {
                int p=__lg(r-l+1);
                return max(st[l][p],st[r-(1<<p)+1][p]);
            };
            f[i][j]+=query(max(j-t,1),min(m,j+t)); //对范围取max/min防止查询越界
            ans=max(ans,f[i][j]);
        }
    }
    printf("%d\n",ans);
    return 0;
}

AC 记录