luogu P1736 创意吃鱼法

心已赠人 2023-06-01 15:54 7阅读 0赞

#  #

luogu P1736 创意吃鱼法

[P1736 创意吃鱼法][P1736]

这道题目如果做过最大正方形的就会比较简单，可是我却完全不会，这道题目只是把对角线的转移改为了是 \\(1\\) 情况下的转移，然后在从右上多做一遍。

具体思路见[这里][Link 1]

#include<bits/stdc++.h> using namespace std; const int N=2501; short int f[N][N],b[N][N],c[N][N]; bool a[N][N]; int n,m,maxx; inline int max(int x,int y) {return x>y ? x:y;} inline int min(int x,int y) {return x<y ? x:y;} int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",a[i]+j); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { if (!a[i][j]) { b[i][j]=b[i][j-1]+1; c[i][j]=c[i-1][j]+1; } if (a[i][j]) f[i][j]=min(f[i-1][j-1],min(b[i][j-1],c[i-1][j]))+1; maxx=max(maxx,f[i][j]); } memset(f,0,sizeof(f)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); for (int i=1;i<=n;i++) for (int j=m;j>=1;j--) { if (!a[i][j]) { b[i][j]=b[i][j+1]+1; c[i][j]=c[i-1][j]+1; } if (a[i][j]) f[i][j]=min(f[i-1][j+1],min(b[i][j+1],c[i-1][j]))+1; maxx=max(maxx,f[i][j]); } printf("%d\n",maxx); return 0; }

需要注意的是这题空间非常容易爆炸，因为如果全开 \\(int\\) 的话，必要的三个数组就有 \\(70M\\) 多，如果输入的数组再开 \\(int\\) 的话就可能炸了。所以因为最大数据不会超过\\(2501\\)可以使用 \\(short\\ int\\) ，格式控制符为\\(\\%hd\\)，字节数为 \\(int\\) 的一半。

转载于:https://www.cnblogs.com/last-diary/p/11546849.html

[P1736]: https://www.luogu.org/problem/P1736
[Link 1]: https://www.cnblogs.com/last-diary/p/11450973.html_

发表评论取消回复

表情：

评论列表（有 0 条评论，7人围观）

还没有评论，来说两句吧...

相关阅读

相关吃鱼还是吃肉 (10 分)

吃鱼还是吃肉 (10 分) ![fish.JPG][] ![肉.JPG][.JPG] 国家给出了 8 岁男宝宝的标准身高为 130 厘米、标准体重为 27 公斤；8 岁

缺乏、安全感/ 2023年10月04日 13:50/ 0 赞/ 16 阅读

相关 unity，大鱼吃小鱼

介绍单机大鱼吃小鱼是一款经典的休闲游戏，玩家需要控制一条小鱼，通过吃掉比自己小的鱼来不断成长，同时避开比自己大的鱼的攻击。游戏画面简洁明快，操作简单易上手，是一款适合所

以你之姓@/ 2023年09月25日 22:13/ 0 赞/ 48 阅读

相关 LuoGu P1368 工艺

[LuoGu P1368 工艺][LuoGu P1368] 最小表示法的板子题.这个题可以用\\(n\\:log\_2\\:n\\)的\\(SA\\)求最小表示法也可以用更

雨点打透心脏的1/2处/ 2023年06月02日 11:59/ 0 赞/ 20 阅读

相关 luogu P1736 创意吃鱼法

luogu P1736 创意吃鱼法 [P1736 创意吃鱼法][P1736] 这道题目如果做过最大正方形的就会比较简单，可是我却完全不会，这道题目只是把对角线的转移

心已赠人/ 2023年06月01日 15:54/ 0 赞/ 8 阅读

相关 P1736-创意吃鱼法

1 include <bits/stdc++.h> 2 define maxn 13003 3 define _for(i,a,b) for(int

怼烎@/ 2023年06月01日 08:51/ 0 赞/ 15 阅读

相关 P1508-Likecloud-吃、吃、吃

1 include <bits/stdc++.h> 2 define maxn 13003 3 define _for(i,a,b) for(int

た入场券/ 2023年06月01日 08:51/ 0 赞/ 11 阅读

相关洛谷 P1736 创意吃鱼法

题目描述回到家中的猫猫把三桶鱼全部转移到了她那长方形大池子中，然后开始思考：到底要以何种方法吃鱼呢（猫猫就是这么可爱，吃鱼也要想好吃法 ^\_\）。她发现，把大池子视为

女爷i/ 2022年05月27日 11:17/ 0 赞/ 186 阅读

相关洛谷 P1508 Likecloud-吃、吃、吃

题目背景问世间，青春期为何物？答曰：“甲亢，甲亢，再甲亢；挨饿，挨饿，再挨饿！” 题目描述正处在某一特定时期之中的李大水牛由于消化系统比较发达，最近一直处

落日映苍穹つ/ 2022年05月27日 03:15/ 0 赞/ 196 阅读

相关 [Luogu P1542] 包裹快递

[原题链接qwq][qwq] \\(Structure\\) 本题要求我们求出 `车的最大速度最小值` 。像求 `最大值最小`、`最小值最大` 这种类型的题目，我们

刺骨的言语ヽ痛彻心扉/ 2021年10月25日 11:57/ 0 赞/ 316 阅读

相关 LuoGu P1006 传纸条

[题目传送门][Link 1] 这题嘛...方格取数和这题一样一样的只不过这题是从左上到右下再回去罢了（来回一趟和来两趟有区别么？没有，那么这题和上题用一样的转移和状态就

你的名字/ 2021年10月01日 03:50/ 0 赞/ 264 阅读