2025-08-28 14:48 广州市番禺区大石大山学校 C++ 发布于广东
关注
洛谷 P1004 解题报告
因为题目要选2次，可是2维DP在这里就是贪心，这样只能选出1次的最大值
考虑四维DP,dp[i][j][k][l]表示第一遍走到点[ i , j ],第二遍走到点[ k , l ]的最优解，那么这个答案可以从dp[i-1][j][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]中转移过来(4个中的最大值加上a[i,j],a[k,l]这两个点的值，如果[i,j]=[k,l]，那就还要减去1个a[i,j])
那么这题就很简单了
如果你觉得有帮助你理解DP的话，可以送一朵小花花哦qwq~
考虑四维DP,dp[i][j][k][l]表示第一遍走到点[ i , j ],第二遍走到点[ k , l ]的最优解，那么这个答案可以从dp[i-1][j][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]中转移过来(4个中的最大值加上a[i,j],a[k,l]这两个点的值，如果[i,j]=[k,l]，那就还要减去1个a[i,j])
那么这题就很简单了
如果你觉得有帮助你理解DP的话，可以送一朵小花花哦qwq~
全部评论
ruixi20140528
广东实验中学 算法工程师
送了哦
相关推荐
点赞 评论 收藏
分享
查看9道真题和解析 点赞 评论 收藏
分享
02-10 10:11
门头沟学院 前端工程师 
钱嘛数字而已：
辅导员肯定不能同意，不然你出事了，他要承担责任。但是，脚和脑子都长在你自己身上，使用它还需要向辅导员报告么？
辅导员必须按流程拒绝你，然后你拿出成年人的态度，做自己的选择。 点赞 评论 收藏
分享