題意：
? ? ? 給你一個圖，讓你找到最大的子矩形。
思路：

? ? ? 之前做過一個最大子矩陣，記得當(dāng)時是用三種方法做的，兩種都是瓶頸法，第三種是dp，結(jié)果今天的用瓶頸吧怎么都過不去，哎！不知道為什么，后來沒辦法有寫了和dp順利ac了，我們求最大子矩陣的時候是記錄最大的長*寬，這次只要記錄最大的min(長,寬),就行了，說下這個題目的dp做法吧，只要是開三個數(shù)組，L[],R[],sum[],sum是記錄當(dāng)前點的上面有多少個連續(xù)的1，L是記錄當(dāng)前點sum大于等于左邊的最遠的那個數(shù)的下標(biāo)（連續(xù)大于），R則是又邊，則我們可以一邊更新sum一邊更新L,R和ans，主要核心如下

for(i = 1 ;i <= n ;i ++)
{
? ?for(j = 1 ;j <= n ;j ++)
? ?map[i][j] == '.' ? sum[j] ++ : sum[j] = 0;//更新當(dāng)前點上面有多少個連續(xù)1
? ?//更新當(dāng)前點左邊連續(xù)大于的最遠
? ?L[1] = 1;
? ?for(j = 2 ;j <= n ;j ++)
? ?{
? ? ? int k = j;
? ? ? while(k > 1 && sum[j] <= sum[k-1]) k = L[k-1];
? ? ? L[j] = k;
? ?}
? //更新當(dāng)前點右邊連續(xù)大于的最遠
? ?R[1] = n;
? ?for(j = n - 1 ;j >= 1 ;j --)
? ?{
? ? ? int k = j;
? ? ? while(k > 1 && sum[j] <= sum[k+1]) k = R[k+1];
? ? ? R[j] = k;
? ?}
? // 更新答案
? for(j = 1 ;j <= n ;j ++)
? {
? ? ?int now = min(R[j] - L[j] + 1 ,sum[j]);
? ? ?if(ans < now) ans = now;
? }
} ?

ok核心就是這些，時間復(fù)雜度是O(n^2)

#include<stdio.h> #include<string.h> int L[1111] ,R[1111] ,sum[1000]; int map[1111][1111];int minn(int x ,int y) {return x < y ? x : y; }int main () {int n ,m ,i ,j;int ans ,x ,y;while(~scanf("%d %d" ,&n ,&m)){memset(map ,255 ,sizeof(map));memset(sum ,0 ,sizeof(sum));while(m--){scanf("%d %d" ,&x ,&y);map[x][y] = 0;}for(ans = 0 ,i = 1 ;i <= n ;i ++){for(j = 1 ;j <= n ;j ++)map[i][j] ? sum[j] ++ : sum[j] = 0;L[1] = 1;for(j = 2 ;j <= n ;j ++){int k = j;while(k > 1 && sum[j] <= sum[k-1]) k = L[k-1];L[j] = k;}R[n] = n;for(j = n - 1 ;j >= 1 ;j --){int k = j;while(k < n && sum[j] <= sum[k+1]) k = R[k+1];R[j] = k;}for(j = 1 ;j <= n ;j ++){int now = minn(R[j] - L[j] + 1 ,sum[j]);if(ans < now) ans = now;}}printf("%d\n" ,ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu4846 最大子正方形(dp)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。