用动态规划wancheng程序1.有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“*”。游戏第1步，将一条边删除。随后n-1步按以下方式操作： (1)选择一条边E以及由E连接着的2个顶点V1和V2； (2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。新顶点的值为顶点V1和V2的整数值通过边E上的运算得到的值。 最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。

这道题可以用动态规划来解决。我们定义 $f_{i,j,0/1}$ 表示将区间 $[i,j]$ 合并起来得到的最大/最小值，其中 $0$ 表示最大值，$1$ 表示最小值。同时，我们在原序列两端各加入一个数，令 $a_0=a_n=1$，这样就可以将多边形变成一个环。

根据动态规划的思想，我们考虑将问题划分成若干个子问题，然后利用子问题的结果推导出原问题的结果。我们可以枚举区间 $[i,j]$ 中最后一条被删除的边的位置 $k$，那么就可以将原问题划分成两个子问题，即将区间 $[i,k]$ 和 $[k,j]$ 分别合并起来，然后再用边 $k$ 的运算符合并这两个子问题。具体地，我们有以下状态转移方程：

$$
\begin{aligned}
f_{i,j,0}&=\max_{i\leq k<j}(f_{i,k,0}\ \text{运算符}\ f_{k+1,j,0})\ \text{或}\ \max_{i\leq k<j}(f_{i,k,1}\ \text{运算符}\ f_{k+1,j,1})\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\text{(对应的运算符为“+”)}\\
f_{i,j,1}&=\min_{i\leq k<j}(f_{i,k,0}\ \text{运算符}\ f_{k+1,j,0})\ \text{或}\ \min_{i\leq k<j}(f_{i,k,1}\ \text{运算符}\ f_{k+1,j,1})\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\text{(对应的运算符为“*”)}
\end{aligned}
$$

初始状态为 $f_{i,i,0}=f_{i,i,1}=a_i$。最终答案为 $f_{1,n,0}$。

时间复杂度为 $O(n^3)$，可以通过此题。以下是代码实现：