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
广东实验中学 算法工程师
送了哦
相关推荐
08-28 14:52
安徽大学 硬件开发 
投递海信集团等公司10个岗位 点赞 评论 收藏
分享