題目描述
回到家中的貓貓把三桶魚全部轉移到了她那長方形大池子中,然后開始思考:到底要以何種方法吃魚呢(貓貓就是這么可愛,吃魚也要想好吃法 ^_*)。她發現,把大池子視為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
輸出格式:
只有一個整數——貓貓一口下去可以吃掉的魚的數量,占一行,行末有回車。
--------------------------------------------我是分割線------------------------------------------------
這題我用的是N2logN的二分,還挺好寫的,效率也很可觀。
進入正題:
首先要對角線要分成兩種,一種是/這樣的,一種是\這樣的(靈魂題解~~),這是兩個相似的問題,我們可以先解決一個,然后把代碼復制一下(嘿嘿嘿)。
我們來看一下\這樣的對角線,式子很明顯:
f[i][j]表示以(i,j)為終點的對角線長度,因此這里一定有要魚
如果矩陣(i-x,j-x,i,j)是滿足題目要求的,那么f[i][j]=max(f[i][j],x)。
同時我們發現,1.x越大越好。2.x的上界是f[i-1][j-1],因為超過這個一定不滿足要求。3.如果x不滿足要求,那么x到其上界就都不滿足。
似乎滿足單調性?
那么我們可以二分x。
之后我們再來看滿足題目要求的矩陣
舉個例子:
1 0 0 0
0 1 0 1
0 0 1 0
0 0 0 1
當i=4,j=4時,由于我們之前算出來f[3][3]是三,那么矩陣(1,1,3,3)一定是符合要求的,所以我們只需要判斷第i行1到j個元素與第j行1到i個元素有沒有魚就可以了。
但如果暴力算的話會T,我們可以算矩陣(i-x,j-x,i,j)的和是不是x+1。于是就可以用到我們的二維前綴和了。
貼一下代碼:
?
#include<cstdio> #include<cstring> #include<iostream> using namespace std; int f[2501][2501],s[2501][2501],i; int a[2501][2501],n,m,l,r,mid,ans,j; inline int read(){int x=0,p=1; char ch=getchar();while (ch<'0'||ch>'9') {if (ch == '-') p=-1; ch=getchar();}while (ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();}return x*p; } int main(){n=read(); m=read();for (i=1; i<=n; i++)for (j=1; j<=m; j++){a[i][j]=read();s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];}for (i=1; i<=n; i++)for (j=1; j<=m; j++){if (a[i][j]){f[i][j]=1;if (f[i-1][j-1]){l=0; r=f[i-1][j-1];while (l<=r){mid=l+r>>1;if (s[i][j]-s[i-mid-1][j]-s[i][j-mid-1]+s[i-mid-1][j-mid-1]==mid+1)l=mid+1;else r=mid-1;}f[i][j]=max(f[i][j],l);}}ans=max(ans,f[i][j]);}memset(f,0,sizeof(f));for (i=1; i<=n; i++)for (j=m; j>=1; j--){if (a[i][j]){f[i][j]=1;l=0; r=f[i-1][j+1];while (l<=r){mid=l+r>>1;if (s[i][j+mid]-s[i][j-1]-s[i-mid-1][j+mid]+s[i-mid-1][j-1]==mid+1)l=mid+1;else r=mid-1;}f[i][j]=max(f[i][j],l);}ans=max(ans,f[i][j]);}printf("%d",ans);return 0; }
?