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
广东实验中学 算法工程师
送了哦
相关推荐
03-19 01:17
大连东软信息学院 人工智能 
在打卡的大老虎很想潜...：你在找实习，没啥实习经历，技术栈放前面，项目多就分两页写，太紧凑了，项目你最多写两个，讲清楚就行，项目背景。用到的技术栈、亮点、难点如何解决，人工智能进面太难了，需求少。你可以加最新大模型的东西 点赞 评论 收藏
分享
查看15道真题和解析 点赞 评论 收藏
分享