题目传送门：P14976 [USACO26JAN1] Photoshoot B

人生第一场 USACO 只做出来铜组 T3。哈哈。

题目分析

注意到每个位置的权值单调不降，所以答案一定单调不降。

考虑前缀和，令 $s_{i,j}$ 表示以 $(i,j)$ 为左上角的照片，发现更新 $a_{r,c}$ 时只有满足 $r \leqslant i < r+k$ 且 $c \leqslant j < c+k$ 的 $s_{i,j}$ 会更新。注意到数据范围很小，直接枚举这些地方更新增量，同时更新答案即可。

最初所有权值都是 $0$，所以不用预处理。时间复杂度 $O(qk^2)$。

代码实现

#include<iostream>
using namespace std;
int n,k,q;
int r,c,v;
int a[505][505],s[505][505],ans;
int main(){
    cin>>n>>k>>q;
    while(q--){
        cin>>r>>c>>v;
        for(int i=r;i<=min(r+k-1,n);i++)
            for(int j=c;j<=min(c+k-1,n);j++){
                s[i][j]+=v-a[r][c];
                ans=max(ans,s[i][j]);
            }
        a[r][c]=v;
        cout<<ans<<'\n';
    }
    return 0;
}

AC 记录。