多边形

· · 个人记录

类型：区间dp

方法：把多边形拆成链，复制一条接在后面，则在区间i到i+n-1的最大值即为所求，i取值1~n。

设计状态f[l][r][0]来记录最大值，f[l][r][1]来记录最小值。则可得到转移方程为

当opt为'+'时，f[l][r][0]=max(f[l][r][0],f[l][k][0]+f[k+1][r][0]),f[l][r][1]=min(f[l][r][1],f[l][k][1]+f[k+1][r][1]) k的取值范围为[l,r)

当opt为''时，设maxx和minn分别为$f[l][k][0]f[k+1][r][0],f[l][k][1]f[k+1][r][0],f[l][k][0]f[k+1][r][1],f[l][k][1]*f[k+1][r][1]的最大值和最小值，则f[l][r][0]=max(f[l][r][0],maxx),f[l][r][1]=min(f[l][r][1],minn)$ k的取值范围为[l,r)