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

这是一个典型的动态规划问题。我们可以用dp[i][j]表示从第i个点到第j个点所能得到的最大值，其中i和j之间的边已经被删除。然后我们需要枚举最后一条被删除的边，假设它连接了第k个点和第k+1个点，那么我们可以将其拆分为两个子问题：dp[i][k]和dp[k+1][j]，然后将它们的结果相加，再加上第k个点和第k+1个点通过这条边得到的值，即val[k][k+1]（val[i][j]表示第i个点和第j个点通过边上的运算得到的值）。

因此，我们可以得到状态转移方程：

dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + val[k][k+1])

注意，我们需要先枚举较小的区间长度len，再枚举左端点i，然后计算右端点j。最终的答案即为dp[1][n]。

同时，我们需要记录转移时的决策，即最后一条被删除的边，可以用pre[i][j]表示从第i个点到第j个点所能得到的最大值的决策，即最后一条被删除的边连接的两个点。在转移时更新pre[i][j]即可。

以下是代码实现：