[luoguP1736] 创意吃鱼法（DP）

传送门

f[i][j][0] 表示从右下角到左上角，以（i，j）为起点能延伸的最大值

f[i][j][1] 表示从左下角到右上角，以（i，j）为起点能延伸的最大值

up[i][j] 表示（i，j）上面有多少个0

left[i][j] 表示（i，j）左边有多少个0

right[i][j] 表示（i，j）右边有多少个0

f[i][j][0] = min(f[i 1][j 1][0], up[i][j], left[i][j]) + 1

f[i][j][1] = min(f[i 1][j + 1][1], up[i][j], right[i][j]) + 1

代码

#include <cstdio> #include <iostream> #define N 2510 #define max(x, y) ((x) > (y) ? (x) : (y)) #define min(x, y) ((x) < (y) ? (x) : (y)) int n, m, ans; unsigned short up[N][N], left[N][N], right[N][N], f[N][N][2]; bool a[N][N]; inline int read() int main() for(i = 1; i <= n; i++) for(j = m; j >= 1; j) right[i][j] = a[i][j + 1] ? 0 : right[i][j + 1] + 1; for(i = 1; i <= n; i++) for(j = 1; j <= m; j++) printf("%d\n", ans); return 0; }

　　

上一篇：[luoguP1072] Hankson 的趣味题（数论）

下一篇：[luoguP1069] 细胞分裂（数论）

---

DP