题目链接: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;
}