P1736 创意吃鱼法 /// DP

题目大意：

https://www.luogu.org/problemnew/show/P1736

题解

dplr[][] 当前点左边（副对角线时为右边）有多少个连续的0

dpup[][] 当前点上边有多少个连续的0

dp[][] 当前点左上有多少个连续的符合要求的1

主对角线时 dp[ i ][ j ]=min(dp[ i-1 ][ j-1 ],min(dplr[ i ][ j-1 ],dpup[ i-1 ][ j ]))+1;

如

原数组　　dplr[][] 　dpup[][]　　dp[][]

1 0 0　　　0 1 2　 0 1 1　　　1 0 0

0 1 0　　　1 0 1　 1 0 2　　　0 2 0

1 0 1　　　0 1 0　 0 1 0　　　1 0 2

首先对于一个正方形矩阵来说其边长上鱼的个数和对角线上鱼的个数是相等的

所以 dp[ i ][ j ] 在 dp[ i-1 ][ j-1 ]、dplr[ i ][ j-1 ]、dp[ i-1 ][ j ] 中取小

相当于查看其左上的 [i-1][j-1]子矩阵、第i行当前点以左、第j列当前点以上符合要求的长度

#include <bits/stdc++.h>

using namespace std;

int n,m,a[][],dp[][];

int dplr[][],dpup[][];

int main()

{

    while(~scanf("%d%d",&n,&m)) {

        int ans=;

        memset(dp,,sizeof(dp));

        memset(dplr,,sizeof(dplr));

        memset(dpup,,sizeof(dpup));

        for(int i=;i<=n;i++)

            for(int j=;j<=m;j++) { /// 主对角线

                scanf("%d",&a[i][j]);

                if(a[i][j])

                    dp[i][j]=min(dp[i-][j-],min(dplr[i][j-],dpup[i-][j]))+;

                else {

                    dplr[i][j]=dplr[i][j-]+;

                    dpup[i][j]=dpup[i-][j]+;

                }

                ans=max(ans,dp[i][j]);

            }

        memset(dp,,sizeof(dp));

        memset(dplr,,sizeof(dplr));

        memset(dpup,,sizeof(dpup));

        for(int i=;i<=n;i++)

            for(int j=m;j>=;j--) { /// 副对角线

                if(a[i][j])

                    dp[i][j]=min(dp[i-][j+],min(dplr[i][j+],dpup[i-][j]))+;

                else {

                    dplr[i][j]=dplr[i][j+]+;

                    dpup[i][j]=dpup[i-][j]+;

                }

                ans=max(ans,dp[i][j]);

            }

        printf("%d\n",ans);

    }

    return ;

}

巴特西

P1736 创意吃鱼法 /// DP

最新文章

热门文章