题解：P15558 [CCPC 2025 哈尔滨站] 扫雪

· · 题解

解题思路：

疑似签到模拟。

注意到，雪可以从左往右、从上往下无代价移动。

我们逐行处理，对于每一行，我们贪心地保留可以弥补负数位置的坑。

具体地，我们从后往前遍历，维护当前后缀需要填坑的雪量 x。

负数表示该位置需要填雪，累加到累加器；

正数则表示可以用于给后缀额外填雪，从 x 中扣除该部分可以贡献的雪量。

处理该行后，对于无法弥补的雪量，因为无法从后边行获取，我们需要付出代价填充；对于额外的雪量，我们可以累计到下一行。

对于最后一行，单独特殊计算。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1005;
ll a[maxn][maxn];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        cin>>a[i][j];
        ll ans=0;
        ll x,y;
        for(int i=1;i<=n;++i){
        x=0;
        for(int j=m;j>=1;--j){
        if(a[i][j]<0)
        x-=a[i][j];
        else{
            y=min(x,a[i][j]);
            a[i][j]-=y;
            x-=y;
        }
    }
    ans+=x;
    if(i==n){
        for(int j=m;j>=1;--j)
        if(a[i][j]>0)
        ans+=a[i][j];
        break;
    }
    for(int j=m;j>=1;--j)
        if(a[i][j]>0)
        a[i+1][j]+=a[i][j];
    }
    cout<<ans<<'\n';
    }
    return 0;
}