P1950

P1950 长方形 看完题解有所启发的一个另解。 考虑对于每一行，底边在这一行上的方案数。然后考虑枚举高度 $h$。底边可以取的范围可以抽象成若干个连续段，底边只能在这几个连续段中取。那么考虑先递推求出一个点可以往上延申多少格，然后从 $n$ 到 $1$ 枚举高度 $h$，维护连续段以及加入延申格式 ......