题解 | 收集金币 | 有限制的dp

对于不可达的(i,j)我们进行标记，它即无法传递给右边的，也或者是下边的

在这种情况下进行dp

找出所有非标记点中最大的金币数就是答案

void solve() {
    int n,m;
    cin>>n>>m;
	//创建mat,lmat记录金币和不可抵达时的回合数
    vector<vector<int>>mat(n+1,vector<int>(m+1,0));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mat[i][j];
        }
    }
    int t;
    cin>>t;
    vector<vector<int>>lmat(n+1,vector<int>(m+1,-INF));
    while(t--){
        int x,y,l;
        cin>>x>>y>>l;
        lmat[x][y]=l;
    }
    vector<vector<int>>dp(n+1,vector<int>(m+1));
    dp[1][1]=mat[1][1];  
    int ans=dp[1][1];

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i==1 && j==1) continue;  
            bool canReach = true;
            if(lmat[i][j] != -INF){
                int steps = i + j - 2; 
				//以(1,1)为起点，到达(i,j)所需回合数steps为i+j-2;
				//变成不可达先于我们的行动  等于也是不可达的
                if(steps >= lmat[i][j]){
                    canReach = false; 
                }
            }
            
            if(!canReach){
                dp[i][j] = -INF; 
                continue;
				//不可达直接拜拜，无论如何也站不到这个点
				//用-INF表示为不可达
            }
            
            int fromLeft = -INF;
            if(j > 1 && dp[i][j-1] != -INF){
                fromLeft = dp[i][j-1] + mat[i][j];
            }
            
            int fromTop = -INF;
            if(i > 1 && dp[i-1][j] != -INF){
                fromTop = dp[i-1][j] + mat[i][j];
            }
            //可以从上面或者左面到达(i,j)
			//不可达的直接是-INF
			//i>1 和 j>1用来初始化i=1和j=1的情况
            dp[i][j] = max(fromLeft, fromTop);
            ans = max(ans, dp[i][j]);
        }
    }
    cout<<ans;
}