hdu4846 最大子正方形(dp)

题意：
      给你一个图，让你找到最大的子矩形。
思路：

      之前做过一个最大子矩阵，记得当时是用三种方法做的，两种都是瓶颈法，第三种是dp，结果今天的用瓶颈吧怎么都过不去，哎！不知道为什么，后来没办法有写了和dp顺利ac了，我们求最大子矩阵的时候是记录最大的长*宽，这次只要记录最大的min(长,宽),就行了，说下这个题目的dp做法吧，只要是开三个数组，L[],R[],sum[],sum是记录当前点的上面有多少个连续的1，L是记录当前点sum大于等于左边的最远的那个数的下标（连续大于），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;//更新当前点上面有多少个连续1
   //更新当前点左边连续大于的最远
   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[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核心就是这些，时间复杂度是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; }

总结

以上是生活随笔为你收集整理的hdu4846 最大子正方形(dp)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。