题解 | 收集金币

#include<bits/stdc++.h>
using namespace std;
int inn[1005][1005];
#define int long long //这题没想到要开长整型弄半天

void solve() {
    int n,m;cin>>n>>m;
    vector<vector<int>>a(n+1,vector<int>(m+2,0));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) cin>>a[i][j];
    }
    vector<vector<int>>dp(n+1,vector<int>(m+1,-1e9));//给个非常大的负数，模拟无法达到的情况
    int t;cin>>t;
    while(t--){
        int x,y,v;cin>>x>>y>>v;
        inn[x][y]=v;
    }
    dp[1][1]=a[1][1];//一定要拎出来否则如果起点变成墙就会改变起点dp的值（变成-1e9），之前一直放在循环里导致一直无法AC
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i==1&&j==1) continue;
            if(inn[i][j]>0&&inn[i][j]<=i+j-2) a[i][j]=-1e9;
            dp[i][j]=max(dp[i][j-1],dp[i-1][j])+a[i][j];
        }
    }
    int max_dp=0;//把所有负值抛弃
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) max_dp=max(max_dp,dp[i][j]);//求最大dp也要拎出来，如果也放在循环里就会把本该走不通的地方变成好像能走通的地方
    }
    cout<<max_dp;
}