[luoguP1736] 创意吃鱼法(DP)
2024-10-19 23:41:11
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 x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
} int main()
{
int i, j;
n = read();
m = read();
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
{
f[i][j][0] = f[i][j][1] = a[i][j] = read();
up[i][j] = a[i - 1][j] ? 0 : up[i - 1][j] + 1;
left[i][j] = a[i][j - 1] ? 0 : left[i][j - 1] + 1;
}
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++)
{
if(!a[i][j]) continue;
f[i][j][0] = min(f[i - 1][j - 1][0], min(up[i][j], left[i][j])) + 1;
f[i][j][1] = min(f[i - 1][j + 1][1], min(up[i][j], right[i][j])) + 1;
ans = max(ans, max(f[i][j][0], f[i][j][1]));
}
printf("%d\n", ans);
return 0;
}
最新文章
- JAVA-多屏幕显示
- Sping mvc 环境下使用kaptcha 生成验证码
- 点击Cell中的按钮时,如何取所在的Cell
- webstorm 自定义代码模板
- git push default
- android 数据库的创建
- 关于C/C++中的位运算技巧
- [Oracle]查看和修改连接数
- Codeforces 510B Fox And Two Dots 【DFS】
- POJ 3047 Bovine Birthday 日期定周求 泽勒公式
- 基于 Hexo + GitHub Pages 搭建个人博客(二)
- 还在用Synchronized?Atomic你了解不?
- java操作Maven
- Coursera Deep Learning 2 Improving Deep Neural Networks: Hyperparameter tuning, Regularization and Optimization - week3, Hyperparameter tuning, Batch Normalization and Programming Frameworks
- xshell与xftp使用注意
- DIV+CSS兼容解决DIV最大宽度和最小宽度问题
- UltraEdit程序设置添加到右键菜单
- mapjoin与reducejoin
- Jmeter(二)参数化
- 二维离散余弦变换(2D-DCT)