关于长方形个数统计公式的理解,不是很清楚,求助;
  • 板块P1950 长方形
  • 楼主KouMoSir
  • 当前回复7
  • 已保存回复7
  • 发布时间2023/7/10 18:00
  • 上次更新2023/11/3 10:42:12
查看原帖
关于长方形个数统计公式的理解,不是很清楚,求助;
1019606
KouMoSir楼主2023/7/10 18:00

看深进这本书的解法;

left数组统计左边第一个小于等于i高度的下标;

right数组统计右边第一个小于i高度的下标;

然后当前i向左和向右延伸能构成的“长方形”数量就等于:

area=h[i]*(i-left[i])*(right[i]-i);

按照这个方法处理我们题目中的样例

....
.***
.*..
.***
...*
.***

那么它每一行能得到的长方形数量是:

10
2
6
4
10
6

我不理解,

第一行, 一个高为1,宽为4的长方形怎么能得到10种不同的长方形剪法。

第二行 一个高为2,宽为1的长方形怎么得到两种不同的长方形剪法。

求助大佬解答思路,能按照样例讲一讲思路就好。

2023/7/10 18:00
加载中...