P1736 创意吃鱼法【dp】

时间：2020-03-20 17:05:10 阅读：57 评论：0 收藏：0 [点我收藏+]

题目描述

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

输出格式

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

输入输出样例

输入 #1

4 6
0 1 0 1 0 0
0 0 1 0 1 0
1 1 0 0 0 1
0 1 1 0 1 0

输出 #1

说明/提示

右上角的

1 0 0
0 1 0
0 0 1

思路
　　考虑这样一个问题：如果以 f[i][j][1|0] 来表示取到第 (i, j) 个位置时所能取到的最长的对角线长度，0表示左上到右下，1表示右上到左下方向，什么时候\怎样来更新 f 的值。
　　首先如果以 之前那道最大正方形的方法来做，只能过第一个点 1 1 0 这个数据。因为会发现这道题比最大正方形多了一个限制条件，就是在这个对角线确定的大矩形中，除了这条对角线之外不能有多余的1.
　　所以在从右上或左上转移时，要多加一个这个条件对状态的影响。
　　这个条件有什么影响？
　　注意到因为动态规划是由 1 ~ n 这样来推理，所以可以分析在边界 1 时的影响即可。
　　对于以下样例分析
　　1 0 0
　　0 1 0
　　0 0 1
　　当 i = 1, j = 1 时，显然 f = 1
　　当 i = 2, j = 2 时，如果 a[2][2] 的上方和右方都没有 1 ，则 f[i][j] = f[i-1][j-1] + 1 ;
　　　　　　　　　　　　　 如果 a[2][2] 的右方和上方有 1 ，显然 f[i][j] = 1 且应该作为一段新的开始。
　　由是可以推到 n 。

CODE

#include <bits/stdc++.h>
#define dbg(x) cout << #x << "=" << x << endl
#define eps 1e-8
#define pi acos(-1.0)

using namespace std;
typedef long long LL;

const int inf = 0x3f3f3f3f;

template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<‘0‘||c>‘9‘)if(c==‘-‘)flag=-1;res=c-‘0‘;
    while((c=getchar())>=‘0‘&&c<=‘9‘)res=res*10+c-‘0‘;res*=flag;
}

namespace _buff {
    const size_t BUFF = 1 << 19;
    char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
    char getc() {
        if (ib == ie) {
            ib = ibuf;
            ie = ibuf + fread(ibuf, 1, BUFF, stdin);
        }
        return ib == ie ? -1 : *ib++;
    }
}

int qread() {
    using namespace _buff;
    int ret = 0;
    bool pos = true;
    char c = getc();
    for (; (c < ‘0‘ || c > ‘9‘) && c != ‘-‘; c = getc()) {
        assert(~c);
    }
    if (c == ‘-‘) {
        pos = false;
        c = getc();
    }
    for (; c >= ‘0‘ && c <= ‘9‘; c = getc()) {
        ret = (ret << 3) + (ret << 1) + (c ^ 48);
    }
    return pos ? ret : -ret;
}

const int maxn = 2577;

int n,m;
int a[maxn][maxn];
int f[maxn][maxn][2];

int main()
{
    //freopen("data.txt", "r", stdin);
    read(n);
    read(m);
    for ( int i = 1; i <= n; ++i ) {
        for ( int j = 1; j <= m; ++j ) {
            read(a[i][j]);
        }
    }
    int ans = 0;
    for ( int i = 1; i <= n; ++i ) {
        for ( int j = 1; j <= m; ++j ) {
            if(a[i][j]) {
                int up = 0, rig = 0;
                for ( int k = i - 1; k >= 1; --k ) {
                    if(a[k][j]) {
                        break;
                    }
                    ++up;
                }
                for ( int k = j + 1; k <= m; ++k ) {
                    if(a[i][k]) {
                        break;
                    }
                    ++rig;
                }
                
                f[i][j][1] = min(f[i - 1][j + 1][1], min(up, rig)) + 1;
                //f[i][j][1] = min(f[i - 1][j + 1][1], min(up, rig)) + 1;
            }
            //printf("f[%d][%d]:%d\n",i, j, f[i][j][0]);
            ans = max(ans, max(f[i][j][0], f[i][j][1]));
        }
        for ( int j = m; j >= 1; --j ) {
            int up = 0, lef = 0;
            if(a[i][j]) {
                for ( int k = i - 1; k >= 1; --k ) {
                    if(a[k][j]) {
                        break;
                    }
                    ++up;
                }
                for ( int k = j - 1; k >= 1; --k ) {
                    if(a[i][k]) {
                        break;
                    }
                    ++lef;
                }
                
                f[i][j][0] = min(f[i - 1][j - 1][0], min(up, lef)) + 1;
                // if(i == 3 && j == 6) {
                //     printf("up:%d lef:%d f[3][6][0]:%d\n",up, lef, f[3][6][0]);
                // }
                // if(i == 2 && j == 5) {
                //     printf("up:%d lef:%d f[2][5][0]:%d\n",up, lef, f[2][5][0]);
                // }
                // if(i == 1 && j == 4) {
                //     printf("up:%d lef:%d f[1][4][0]:%d\n",up, lef, f[1][4][0]);
                // }
            }
            ans = max(ans, max(f[i][j][0], f[i][j][1]));
        }
        
    }
    cout << ans << endl;
    return 0;
}

P1736 创意吃鱼法【dp】

原文：https://www.cnblogs.com/orangeko/p/12532328.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)

P1736 创意吃鱼法 【dp】

题目描述

输入格式

输出格式

输入输出样例

说明/提示

P1736 创意吃鱼法【dp】