区间 DP

P4342 [IOI1998]Polygon

断环成链，考虑到乘法负负得正，需要同时维护最大值和最小值，\(f_{i,j}\) 表示区间 \([i,j]\) 的最大价值，\(g_{i,j}\) 表示最小价值。

\[f_{i,j}=\max\{f_{i,k}+f_{k+1,j}\}\\g_{i,j}=\max\{g_{i,k}+g_{k+1,j}\}\\f_{i,j}=\max\{f_{i,k}\times f_{k+1,j},f_{i,k}\times g_{k+1,j},g_{i,k}\times f_{k+1,j},g_{i,k}\times g_{k+1,j}\}\\g_{i,j}=\min\{f_{i,k}\times f_{k+1,j},f_{i,k}\times g_{k+1,j},g_{i,k}\times f_{k+1,j},g_{i,k}\times g_{k+1,j}\} \]