题目链接:https://ac.nowcoder.com/acm/contest/102742/D

1、假如去掉墙这个限制条件,那么本题就变成了经典的线性dp问题,显然令dp[i,j]表示从原点走到(i,j)能得到的最大价值。dp状态转移方程为dp[i][j]=max(dp[i-1],dp[i][j-1])+a[i][j]

2、现在加上墙这个限制条件,假如开始就有墙,那么设置一个标记数组b[i][j],当b[i][j]==1时表示有墙,反之表示没有墙。在情况1的基础上,我们只需要在每次做dp转移的时候判断一下b[i][j]是否等于0,只有b[i][j]等于0的时候才可以转移

3、本题的墙并不是开始就有,而是有时间限制。这里我们观察到,每一次移动只能往右或者往下移动,即每次从(i,j)-->(i+1,j),(i,j)-->(i,j+1)。从(1,1)到(i,j)至少需要i+j-2次移动。因此只需要判断一下v是否大于i+j-2,从而设置2中的b数组,则变成了情况2

 int n,m;
int a[N][N],cost[N][N],dp[N][N];
//dp(i,j)表示从1,1走到i,j所得到的最大收益
void kkk(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
//注意初始化边界
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++){
            dp[i][j]=-INF;
            cost[i][j]=INF;
        }
    int t;
    cin>>t;
    for(int i=1;i<=t;i++){
        int x,y,v;
        cin>>x>>y>>v;
        cost[x][y]=v;
    }

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(cost[i][j]<=i+j-2) a[i][j]=-INF*2;

    dp[1][0]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];

    int res=-1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            res=max(res,dp[i][j]);
    cout<<res<<endl;
}