注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1047】【HAOI2007】【理想的正方形】  

2014-03-12 18:11:00|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   a*b的矩阵找一个n*n的正方形,使得其中的最小数和最大数的差最大。
   WC2014的FHQ神犇的讲义上的?!
   当时前排的神犇说的方法蒟蒻各种听不懂.....自己先YY下,显然最暴力的方法就是枚举...复杂度O(abn^2)。咱们肯定要先暴力出一个正方形吧...考虑对这个正方形扩展成新的正方形(先从左往右,再从下往上),实际上就是从一个n的列或者行找出最大值和最小值,快速选择可以让咱们可以O(n)扩展一个,那么O(abn)应该可以过吧....当然可以用什么数据结构维护这个也可以...然后就是O(ablogn),但是感觉各种违和感.....
    (这道题给咱们一个以后的思路就是分析单调性啥的,顺便加上考虑简单的)
     首先对于每一行的每一个格子,求出其列往上走共n个格子的最大值,然后咱们就把每一个点及其上方n个点的最大值压缩到这个点上,然后咱们再对每一行用单调队列...然后复杂度为O(ab)。即压缩信息!!
     提交的时候WA一次,这题的 数据得开 long long 才可以...不然会超界。
=============================

#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

int w[1010][1010],que[2010],a,b,n;
long long f[2][1010][1010],F[1010][1010],ans;

template <typename T>
 T min(T a,T b){return (a<b)?a:b;}

void init()
{
     scanf("%d%d%d",&a,&b,&n);
     int i,j;
     for (i=1;i<=a;i++)
       for (j=1;j<=b;j++)
         scanf("%d",&w[i][j]);
}

void work(int ww)
{
     memset(que,0,sizeof(que));
     memset(F,0,sizeof(F));
     int i,j;
     for (i=1;i<=b;i++){
         memset(que,0,sizeof(que));
         int l=0,r=-1;
         for (j=1;j<=a;j++) {
             for(;l<=r&&w[que[r]][i]<=w[j][i];r--);
             que[++r]=j;
             for(;l<=r&&que[l]<j-n+1;l++);
             F[j][i]=w[que[l]][i];}}
     for (i=1;i<=a;i++){
         memset(que,0,sizeof(que));
         int l=0,r=-1;
         for (j=1;j<=b;j++){
             for(;l<=r&&F[i][que[r]]<=F[i][j];r--);
             que[++r]=j;
             for(;l<=r&&que[l]<j-n+1;l++);
             f[ww][i][j]=F[i][que[l]];}}
}

int main()
{
    init();
    work(0);
    int i,j;
    for (i=1;i<=a;i++)
     for (j=1;j<=b;j++)
      w[i][j]=-w[i][j];
    work(1);
    ans=1000000000;
    for (i=n;i<=a;i++)
     for (j=n;j<=b;j++)
       ans=min(ans,f[0][i][j]+f[1][i][j]);
    printf("%d",ans);
    return 0;
}
       

     
             
     

     
  评论这张
 
阅读(47)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017