USACO/bigbrn

来自NOCOW

 这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。
 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。
 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。

这是USACO Chapter 5 .3中的OI题目PROB Big Barn的介绍及题解，参见翻译，C语言代码，C++语言代码，Pascal语言代码。

[编辑] 问题分析

[编辑] 动态规划

可参考home on the range一题

状态
- F[i][j] 表示以(i,j)为左上角最大正方形的边长

初始条件
- 如果(i,N)没有障碍 F[i][N]=1 否则 F[i][N]=0
- 如果(N,i)没有障碍 F[N][i]=1 否则 F[N][i]=0

状态转移方程

 if f[i][j]>0 then //(i,j)没有树。
  F[i][j]=min(F[i+1][j],F[i][j+1],F[i+1][j+1])+1;

[编辑] 极大化思想

这题还可以用极大化思想的做，这种方法的延伸性更强一些，但就这题而言，程序比较长，同样是O(n^2)，相比DP没有优势。

这题也可用做到O(N*log(n))级别，方法同IOI一题

补充：这道题目用王知昆所说的第一种方法也能过，而且速度快于第二种方法。。。事实上第一种方法的最坏情况是非常难达到的！具体见我的 Pascal 程序 -- Winter Legend

[编辑] 另一种DP

下面就是方程，还可以用滚动数组优化内存。

k=min(f[i-1][j],f[i][j-1]);
f[i][j]=hash[i-k][j-k]?k:k+1;
ans=max(ans,f[i][j]);

hash[i][j]为true的话，就是（i,j）有树。

                                                                ---------广陵lonely散

[编辑] 二分答案

预算理出每个格子右边最近的树的横坐标。具体看C++代码

[编辑] 二维树状数组+二分

  Test 1: TEST OK [0.000 secs, 10876 KB]
  Test 2: TEST OK [0.000 secs, 10876 KB]
  Test 3: TEST OK [0.000 secs, 10876 KB]
  Test 4: TEST OK [0.000 secs, 10876 KB]
  Test 5: TEST OK [0.000 secs, 10876 KB]
  Test 6: TEST OK [0.000 secs, 10876 KB]
  Test 7: TEST OK [0.011 secs, 10876 KB]
  Test 8: TEST OK [0.011 secs, 10876 KB]
  Test 9: TEST OK [0.032 secs, 10876 KB]
  Test 10: TEST OK [0.065 secs, 10876 KB]
  Test 11: TEST OK [0.054 secs, 10876 KB]
  Test 12: TEST OK [0.065 secs, 10876 KB]
  Test 13: TEST OK [0.097 secs, 10876 KB]
  Test 14: TEST OK [0.065 secs, 10876 KB]
  Test 15: TEST OK [0.130 secs, 10876 KB]

详情参见C++代码

[编辑] 暴力枚举

谁说不行的预处理先，f[i][j]表示第i行开始到第j个有多少个障碍

   for(i=1;i<=n;i++)
    for(j=1;j<=n;j++){
     if(f[i][j])f[i][j]=f[i][j-1]+1;
     else f[i][j]=f[i][j-1];
    }

直接枚举，记录ans来剪枝

   for(i=1;i<=n-ans+1;i++)
    for(j=1;j<=n-ans+1;j++)
     if(f[i][j]==f[i][j-1]){
      u=min(n-i+1,n-j+1);
      bool bo=1;
      for(k=ans;k<=u;k++){
       for(p=i;p<=i+k-1;p++)
        if(f[p][j+k-1]-f[p][j-1]>0){bo=0;break;}
       if(!bo){
         if(k-1>ans)ans=k-1;
         break; }
      }
      if(k>ans&&k>u)ans=k-1;
    }

时间挺可观

  Test 1: TEST OK [0.016 secs, 7352 KB]
  Test 2: TEST OK [0.016 secs, 7352 KB]
  Test 3: TEST OK [0.014 secs, 7352 KB]
  Test 4: TEST OK [0.016 secs, 7352 KB]
  Test 5: TEST OK [0.008 secs, 7352 KB]
  Test 6: TEST OK [0.019 secs, 7352 KB]
  Test 7: TEST OK [0.022 secs, 7352 KB]
  Test 8: TEST OK [0.019 secs, 7352 KB]
  Test 9: TEST OK [0.019 secs, 7352 KB]
  Test 10: TEST OK [0.049 secs, 7352 KB]
  Test 11: TEST OK [0.640 secs, 7352 KB]
  Test 12: TEST OK [0.138 secs, 7352 KB]
  Test 13: TEST OK [0.076 secs, 7352 KB]
  Test 14: TEST OK [0.059 secs, 7352 KB]
  Test 15: TEST OK [0.051 secs, 7352 KB]

[编辑] 参考代码

C

C++

Pascal