题解 | 收集金币

import java.util.*;

public class Main{
    public static final int inf = 0x3f3f3f3f;
    public static int dis(int x, int y){
        return x + y - 2;
    }
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] a = new int[n+5][m+5];
        int[][] f = new int[n+5][m+5];
        int[][] tim = new int[n+5][m+5];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                a[i][j] = in.nextInt();
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                f[i][j] = 0;
                tim[i][j] = inf;
            }
        int t = in.nextInt();
        for(int i=1;i<=t;i++){
            int x, y ,z;
            x = in.nextInt();
            y = in.nextInt();
            z = in.nextInt();
            tim[x][y] = z;
        }
        f[1][1] = a[1][1];
        int ans = 0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                if(dis(i, j) >= tim[i][j]) continue;
                //System.out.println(i + " " + j);
                if(i > 1 && f[i-1][j] != 0) f[i][j] = Math.max(f[i][j], f[i-1][j] + a[i][j]);
                if(j > 1 && f[i][j-1] != 0) f[i][j] = Math.max(f[i][j], f[i][j-1] + a[i][j]);
                ans = Math.max(ans, f[i][j]);
            }
        System.out.println(ans);
    }
}