P1295-创意吃鱼

题目描述

回到家中的猫猫把三桶鱼全部转移到了她那长方形大池子中,然后开始思考:到底要以何种方法吃鱼呢(猫猫就是这么可爱,吃鱼也要想好吃法 ^_*)。她发现,把大池子视为01矩阵(0表示对应位置无鱼,1表示对应位置有鱼)有助于决定吃鱼策略。

在代表池子的01矩阵中,有很多的正方形子矩阵,如果某个正方形子矩阵的某条对角线上都有鱼,且此正方形子矩阵的其他地方无鱼,猫猫就可以从这个正方形子矩阵“对角线的一端”下口,只一吸,就能把对角线上的那一队鲜鱼吸入口中。

猫猫是个贪婪的家伙,所以她想一口吃掉尽量多的鱼。请你帮猫猫计算一下,她一口下去,最多可以吃掉多少条鱼?

输入输出格式

输入格式:

 

有多组输入数据,每组数据:

第一行有两个整数n和m(n,m≥1),描述池塘规模。接下来的n行,每行有m个数字(非“0”即“1”)。每两个数字之间用空格隔开。

对于30%的数据,有n,m≤100

对于60%的数据,有n,m≤1000

对于100%的数据,有n,m≤2500

 

输出格式:

 

只有一个整数——猫猫一口下去可以吃掉的鱼的数量,占一行,行末有回车。


emmmm,刚看到这道题,这不是很显然吗,用f[i][j]表示以(i,j)为正方形的右下角所满足题意的最大正方形的边长,则转移方程为

if(a[i][j] == 1) {
    int x = f[i - 1][j - 1];
    int x1 = i - x, y1 = j - x;
    if(sum[i][j] - sum[x1 - 1][j] - sum[i][y1 - 1] + sum[x1 - 1][y1 - 1] == x + 1) {
        f[i][j] = x + 1;
    }
}

再镜面对称过来,嗯,应该A掉了,提交~~~~     ???嗯?怎么WA了一组,应该是细节问题,调试~~~~~

    两天后......

怎么还没过啊,昧着良心看一下题解吧,wow,竟然有大问题,因为这种做法太过于极端,要不全部保留,要不不保留,所以无法确定该点最大的正方形,应逐一枚举左上那个点的边长,找到能满足的最大值后跳出

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 5e5 + 100;
const int MAXM = 3e3 + 10;

template < typename T > inline void read(T &x) {
    x = 0; T ff = 1, ch = getchar();
    while(!isdigit(ch)) {
        if(ch == -) ff = -1;
        ch = getchar();
    }
    while(isdigit(ch)) {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    x *= ff;
}

template < typename T > inline void write(T x) {
    if(x < 0) putchar(-), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + 0);
}

int n, m, maxx = -INF, a[MAXM][MAXM], b[MAXM][MAXM], sum[MAXM][MAXM], f[MAXM][MAXM];

int main() {
//    freopen("1.in", "r", stdin);
    read(n); read(m);
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            read(a[i][j]);
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
        }
    }
    
/*    for(int len = 1; len <= min(n, m); ++len) {
        for(int i = 1; i <= n - len + 1; ++i) {
            for(int j = 1; j <= m - len + 1; ++j) {
                int x1 = i + len - 1;
                int y1 = j + len - 1;
                if(sum[x1][y1] - sum[i - 1][y1] - sum[x1][j - 1] + sum[i - 1][j - 1] != len * len) continue;
                
            }
        }
    }*/
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(a[i][j] == 1) {
                int x = f[i - 1][j - 1];
                for(int k = x; k >= 0; --k) {
                    int x1 = i - k, y1 = j - k;
                    if(sum[i][j] - sum[x1 - 1][j] - sum[i][y1 - 1] + sum[x1 - 1][y1 - 1] == k + 1) {
                        f[i][j] = k + 1;
                        break;
                    }
                }
            }
            maxx = max(maxx, f[i][j]);
        }
    }
//    memset(sum, 0, sizeof(sum));
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            b[i][j] = a[i][m - j + 1];
//            sum[i][j] = sum[i][m - j + 1];
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + b[i][j];
        }
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(b[i][j] == 1) {
                int x = f[i - 1][j - 1];
                for(int k = x; k >= 0; --k) {
                    int x1 = i - k, y1 = j - k;
                    if(sum[i][j] - sum[x1 - 1][j] - sum[i][y1 - 1] + sum[x1 - 1][y1 - 1] == k + 1) {
                        f[i][j] = k + 1;
                        break;
                    }
                }
            }
            maxx = max(maxx, f[i][j]);
        }
    }
    write(maxx);
    putchar(\n);
    return 0;
}
相关文章
相关标签/搜索
每日一句
    每一个你不满意的现在,都有一个你没有努力的曾经。
公众号推荐
   一个历史类的公众号,欢迎关注
一两拨千金