专栏文章

矩阵DP

CCHkujiu
算法·理论参与者 1已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mip9ueb8
此快照首次捕获于
2025/12/03 08:31
3 个月前
此快照最后确认于
2025/12/03 08:31
3 个月前
查看原文
复习DP四步
  • 问题拆解（分阶段）
  • 状态定义
  • 状态转移方程
  • 算法实现
例题1P1004[NOIP2000提高组]方格取数例题1P1004 [NOIP 2000 提高组] 方格取数
5
4
3
2
1X
12345
dp[阶段][x1][x2]
dp[3][1][3]
dp[x1][y1][x2][y2]
例题2P1006[NOIP2008提高组]传纸条例题2P1006 [NOIP 2008 提高组] 传纸条
↑→→→终点
↑→→→→→→→→→→→↑↑
↑○↑
↑○↑
↑→→→→→→→→→→→→→→→↑
起点
例题3P1434[SHOI2002]滑雪例题3P1434 [SHOI2002] 滑雪
低←高
↑←←↓
dp[i][j]
dp[i][j+1]=max(dp[i][j+1],dp[i][j]+1)
  • 只要到达一个点，就不会返回，满足dp的无后效性，所以可以用dp解决。
  • 这里用到priority_queue，对>重载
例题4P1169[ZJOI2007]棋盘制作例题4P1169 [ZJOI2007] 棋盘制作
j
✖✖
i▓
▓

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...