7614:最低通行费
时间: 2023-08-24 19:06:42 浏览: 63
根据引用\[1\]和引用\[2\]的描述,这个问题可以使用动态规划来解决。我们可以定义一个二维数组dp,其中dp\[i\]\[j\]表示从左上角(1,1)到(i,j)位置的所有路径中,缴纳费用最少的路径的缴纳费用。初始状态为dp\[1\]\[1\],即从(1,1)到(1,1)需要缴纳的费用,为a\[1\]\[1\]。
然后,我们可以使用状态转移方程来计算dp\[i\]\[j\]的值。根据引用\[3\]的描述,商人只能向上下左右四个方向移动且不能离开网格,所以我们可以考虑从上方或左方到达当前位置(i,j)。我们可以选择从上方到达(i,j)的路径或从左方到达(i,j)的路径中缴纳费用较少的那条路径,并将其加上当前位置的费用a\[i\]\[j\],即dp\[i\]\[j\] = min(dp\[i-1\]\[j\], dp\[i\]\[j-1\]) + a\[i\]\[j\]。
最后,我们可以得到从左上角到右下角的所有路径中,缴纳费用最少的路径的缴纳费用为dp\[N\]\[N\],其中N为正方形的宽度。
因此,对于给定的输入,我们可以使用动态规划算法来计算最低通行费。
#### 引用[.reference_title]
- *1* [信息学奥赛一本通 1287:最低通行费 | OpenJudge NOI 2.6 7614:最低通行费](https://blog.csdn.net/lq1990717/article/details/125212152)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^control_2,239^v3^insert_chatgpt"}} ] [.reference_item]
- *2* *3* [19:最低通行费](https://blog.csdn.net/lml11111/article/details/70185998)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^control_2,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]