P736 创意吃鱼法

题目描述回到家中的猫猫把三桶鱼全部转移到了她那长方形大池子中然后开始思考到底要以何种方法吃鱼呢猫猫就是这么可爱吃鱼也要想好吃法 ^_*。她发现把大池子视为01矩阵0表示对应位置无鱼1表示对应位置有鱼有助于决定吃鱼策略。在代表池子的01矩阵中有很多的正方形子矩阵如果某个正方形子矩阵的某条对角线上都有鱼且此正方形子矩阵的其他地方无鱼猫猫就可以从这个正方形子矩阵“对角线的一端”下口只一吸就能把对角线上的那一队鲜鱼吸入口中。猫猫是个贪婪的家伙所以她想一口吃掉尽量多的鱼。请你帮猫猫计算一下她一口下去最多可以吃掉多少条鱼输入格式有多组输入数据每组数据第一行有两个整数n和mn,m≥1描述池塘规模。接下来的n行每行有m个数字非“0”即“1”。每两个数字之间用空格隔开。对于30%的数据有n,m≤100对于60%的数据有n,m≤1000对于100%的数据有n,m≤2500输出格式只有一个整数——猫猫一口下去可以吃掉的鱼的数量占一行行末有回车。输入输出样例输入 #1 复制4 60 1 0 1 0 00 0 1 0 1 01 1 0 0 0 10 1 1 0 1 0输出 #1 复制3说明/提示右上角的1 0 00 1 00 0 1思路此题类似于最大1矩阵 不过需要预处理 需统计连续的横纵的零的个数 再与连续对角1取最小值看能构成的正方形矩阵大小 状态转移方程 dp[i][j] min(dp[i - 1][j - 1], min(heng[i][j - 1], zhong[i - 1][j]))1 和 dp[i][j] min(dp[i 1][j - 1], min(heng[i][j - 1], zhong[i 1][j]))1; 前一个是主对角线的正方形第二个是副对角线的正方形#include iostream #include algorithm #include cstring using namespace std; #define ms(i,j) memset(i,j,sizeof i); const int N 2510; int g[N][N]; int dp[N][N]; int heng[N][N]; int zhong[N][N]; int n, m; int main() { cin n m; int ans0; for (int i 1; i n; i) for (int j 1; j m; j) { scanf(%d, g[i][j]); if (!g[i][j])//看连续的横的零纵的零有多少 { heng[i][j]heng[i][j - 1]1; zhong[i][j] zhong[i - 1][j]1; } else//看01构成的正方形有多大 { dp[i][j] min(dp[i - 1][j - 1], min(heng[i][j - 1], zhong[i - 1][j]))1; ans max(ans, dp[i][j]); } } for (int i 1; i n; i) { for (int j 1; j m; j) cout heng[i][j] ; cout endl; } ms(dp, 0); ms(heng, 0); ms(zhong, 0); for(int in;i0;i--) for (int j 1; j m; j) { if (!g[i][j]) { heng[i][j] heng[i][j - 1]1; zhong[i][j] zhong[i 1][j]1; } else { dp[i][j] min(dp[i 1][j - 1], min(heng[i][j - 1], zhong[i 1][j]))1; ans max(ans, dp[i][j]); } } cout ans endl; system(pause); return 0; }传送门