题解 P1387 【最大正方形】

传送门

搞不清楚为什么这一题要DP . . . . . .

思路：

\(n\le100\)，考虑暴力。
要求一大块区间内都是1，考虑前缀和。
在矩阵中求一个符合条件的子矩阵，考虑\(n^3\)的“压行”做法。

具体实现:

读入时，先记录每一层的前缀和，再把上一次的前缀和加进来。
\(n^2\)枚举正方形的上界和下界，顶着上界下界\(O(n)\)扫描记录答案。
若当前的上界下界的距离\(\le ans\)跳过

直接上代码。用了宏定义和快读，但很好理解，初学者都能一眼就懂..

#include<iostream>

#include<cstring>

#include<queue>

#include<cstdlib>

#include<vector>

#include<set>

#include<map>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<bitset>

#include<ctime>

using namespace std;

#define TMP template < class ins >

#define endl '\n'

#define RP(t,a,b) for(register int t=(a),edd=(b);t<=edd;t++)

#define ERP(t,a) for(register int t=head[(a)];t;t=e[t].nx)

#define DRP(t,a,b) for(register int t=(a),edd=(b);t>=edd;t--)

typedef long long ll;

TMP inline ins qr(ins tag){

    char c=getchar();

    ins x=0;

    int q=0;

    while(c<48||c>57)

	q=c==45?-1:q,c=getchar();

    while(c>=48&&c<=57)

	x=x*10+c-48,c=getchar();

    return q==-1?-x:x;

}

const int maxn=105;

int data[maxn][maxn];

int sum[maxn][maxn];

int n,m;

int ans;

inline void init(){

    n=qr(1);

    m=qr(1);

    RP(t,1,n){

	RP(i,1,m)

	    sum[t][i]=(data[t][i]=qr(1))+sum[t][i-1];

	//记录当前行前缀和

	RP(i,1,m)

	    sum[t][i]+=sum[t-1][i];

	//把上一行前缀和加进来

    }

    return;

}

inline bool jde(int x1,int y1,int x2,int y2){

    int cmp=(abs(x1-x2)+1)*(abs(y1-y2)+1);

    //计算面积

    int sttd=sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];

    //(x1-1,y1-1)到(1,1)的矩阵被减了两次，要补偿回来

    return cmp==sttd;

}

inline void eff(){

    RP(t1,1,n){//枚举上界

	RP(t2,t1,n){//枚举下界

	    int k=t2-t1+1;

	    //计算当前上下界对应的正方形大小

	    if(k<=ans)

		continue;

	    //最优性剪枝

	    RP(t,k,m)//扫描一遍，

		if(jde(t1,t-k+1,t2,t)){

		    ans=k;break;

		    //可以直接记录答案，因为前面已经最优性剪枝了

		}

	}

    }

    cout<<ans<<endl;

}

int main(){

#define debugged

#ifdef debug

    freopen("in.in","r",stdin);

    freopen("out.out","w",stdout);

#endif

    init();

    eff();

    return 0;

}

巴特西

题解 P1387 【最大正方形】

传送门

搞不清楚为什么这一题要DP . . . . . .

最新文章

热门文章