矩阵DP
复习DP四步
- 问题拆解（分阶段）
- 状态定义
- 状态转移方程
-
算法实现
例题1P1004 [NOIP 2000 提高组] 方格取数
| 5 | ||||
|---|---|---|---|---|
| 4 | ||||
| 3 | ||||
| 2 | ||||
| 1 | X | |||
| 1 | 2 | 3 | 4 | 5 |
dp[阶段][x1][x2]
dp[3][1][3]
dp[x1][y1][x2][y2]
| ↑→→→ | 终点 | |||
| ↑→→→ | →→→→ | →→→→ | ↑ | ↑ |
| ↑○ | ↑ | |||
| ↑○ | ↑ | |||
| ↑→→→ | →→→→ | →→→→ | →→→→ | ↑ |
| 起点 |
| 低← | 高 |
| ↑← | ←↓ |
dp[i][j]
dp[i][j+1]=max(dp[i][j+1],dp[i][j]+1)
- 只要到达一个点，就不会返回，满足dp的无后效性，所以可以用dp解决。
-
这里用到priority_queue，对>重载
例题4P1169 [ZJOI2007] 棋盘制作
| j | |
|---|---|
| ✖ | ✖ |
| i | ▓ |
| ▓ | |