SRM-146 RectangularGrid

题目大意：求长n宽m的网格里长方形的个数
思路: 首先想dp，但没有明显的递推公式。那就最直接最暴力的方式：看看能否列举出所有长方形？显然可以。

for(int rect_width=1; rect_width<=Width; rect_width++) {
  for(int rect_height=1; rect_height<=Height; rect_height++) {
      if(rect_width==rect_height) continue;  // 剔除squares
      // 统计(rect_width, rect_height)的长方形个数
      for(int x=0; x+rect_width<=Width; x++) {
          for(int y=0; y+rect_height<=Height; y++) {
              cnt++;
          }
      }
  }
}

四重循环复杂度太高，优化一下。

for(int y=0; y+rect_height<=Height; y++) {
     cnt++;

可以变成：cnt += Height-rect_height+1

for(int x=0; x+rect_width<=Width; x++) {
    cnt+=Height-rect_height+1;
}

变成： cnt += (Width-rect_width+1)*(Height-rect_height+1)
整个程序复杂度从O(N⁴)变为O(N²)，基本也就够了，那能不能再优化？答案是能。
首先把四重循环交换顺序：

for(int rect_width=1; rect_width<=Width; rect_width++) {
    for(int x=0; x+rect_width<=Width; x++) {
        for(int rect_height=1; rect_height<=Height; rect_height++) {
            for(int y=0; y+rect_height<=Height; y++) {
                cnt++;
          }
      }
  }
}

最里面两层循环Height，Height-2，…，3，2，1，累加起来是(Height+1)*Height/2，同理外面的为(Width+1)*Width/2，去掉所有循环后为all+=(Height+1)*Height/2 * (Width+1)*Width/2，但是注意，现在算的不仅有长方形还有正方形。正方形怎么统计呢？利用上面类似的方法，通过代码转换为数学公式更直接些。

for(int rect_width=1; rect_width<=Width; rect_width++) {
  for(int rect_height=1; rect_height<=Height; rect_height++) {
      if(rect_width==rect_height) {
      // 统计(rect_width, rect_height)的长方形个数
      for(int x=0; x+rect_width<=Width; x++) {
          for(int y=0; y+rect_height<=Height; y++) {
              cnt++;
          }
      }
  }
  }
}

显然，正方形的数量可以简化为：

for(int i=1; i<=min(Height, Width); i++) {
  squares+= (Height-i+1)*(Width-i+1)
}

答案all-squares即可。

代码:
略