luogu P 1736創意的な魚の食べ方

970 ワード

$luogu P 1736$魚を食べるアイデア
P 1736創意的な魚の食べ方
この問題は最大正方形をしたことがあると簡単ですが、私は全然できません.この問題は対角線の移行を(1)の場合の移行に変えて、右上から何度もします.
具体的な考え方はここを参照してください.
#include
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=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
",maxx); return 0; }

この空間は爆発しやすいので、全開(int)であれば必要な3つの配列が(70 M)多く、入力した配列が再び(int)であれば爆発する可能性があります.したがって、最大データは(2501)を超えないので、(short/int)、フォーマット制御子は(%hd)、バイト数は(int)の半分を使用できます.