一道神奇的有关网格的DP(一些大佬称其为暴力DP)。
这里将 “I” 字母分为的三个部分称为第一,二,三部分。
做法:设 fi,j,k,l(l∈[1,3]) 表示第 i 行,当前在第 l 部分,区间 [j,k]的最大面积。
由于第二部分必须比第一部分短一截,在暴力的时候就得在枚举第一部分的 j,k 时枚举第二部分的 j,k,pia的一下 n4 了。
于是出现了一个小技巧:使用另一个数组 gi,j,k,l(l∈[1,2]),
gi,jg,kg,1 记录 fi,jf,kf,1|jf∈[1,jg),kf∈(kg,m]的最大值,
gi,jg,kg,2 记录 fi,jf,kf,2|jf,kf∈(jg,kg)的最大值,
这样在不同部分的转移中就可以直接调用 g 数组而不用枚举 jg,kg 了。
最后我们会发现 i 这一维可以被轻松地压掉,但好像可以不压