阅读前需
深剖析分系列是记录我个人的做题思路，实现过程的全面分析，存在内容可靠、思路健全、分析到位、试错纠错等优于一般题解的特征，其中，Quest部分表示探索问题，我会在此提出做题时的想法、问题，并在内容中得到解决，因此建议从上到下按序浏览，以防出现思路断层，内容不衔接的情况，感谢理解与支持！
题目大意
给定一个多边形，对应节点上标记有一个数字，每条边上标记有加（t）或乘（x）表示相邻两个节点可进行的操作，操作后两个节点将合并为一个节点，首先删去一条边（不进行操作），之后在若干次操作后使得该多边形只剩一个节点，且要求所剩节点标记的数最大化，询问最大的数字
题目分析
如图是题目所给出的示例图，我们可以通过模拟该图来得到我们代码实现的过程。
Quest1：如何处理环？
我们先假定删除了某条边，注意这里第一步是删除，并没有进行操作。
然后我们就要一系列的合并操作，完成之后又要换另一条边删掉，继续下去。。。
很明显这是一个很暴力的算法，而对于这种环状的区间dp问题，大家应该能反应出来，我们可以通过破环成链的方法，具体的就是将原本的一个环在复制一遍，形成一个长度为原先二倍的大环，这个时候随便断哪一条边都没有问题了，所以我们下面的操作中默认断掉了第一条边，或者说是第一条输入的边。
Ques2：如何初步验证？
Part1：试验最初思路
之后我们可以开始合并操作，在这道题中，我们应当能发现现在是对一条链进行的区间合并操作，很容易就想到区间dp，因此，我们会用到下述转移方程：
\[f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]) \]不过与常规区间dp的不同之处也显而易见，我们的转移过程中不一定只涉及到加法这一操作，而对于乘法的处理，或许会想到：
\[f[i][j]=max(f[i][j],f[i][k]*f[k+1][j]) \]似乎到这一步就已经大功告成了,于是我们自信满满的打出以下代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,ans=-0x3f3f3f3f;
char op[100];
int dp[200][200];
int main(){
cin >> n;
memset(dp,-0x3f,sizeof dp);
for(int i=1;i<=n;i++){
cin >> op[i-1] >> dp[i][i];
op[i+n-1]=op[i-1];
dp[i+n][i+n]=dp[i][i];
}
for(int len=2;len<=n;len++)
for(int l=1;l<=n;l++){
int r=l+len-1;
for(int k=l;k<r;k++){
if(op[k]=='t') dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]);
if(op[k]=='x') dp[l][r]=max(dp[l][r],dp[l][k]*dp[k+1][r]);
}
}
for(int l=1;l<=n;l++) ans=max(ans,dp[l][l+n-1]);
cout << ans << '\n';
for(int l=1;l<=n;l++) if(ans==dp[l][l+n-1]) cout << l << ' ';
return 0;
}
然后我们成功的wa掉了这道题，还只有二十分。。。
Part2：找到问题所在
我们很容易可以发现，这道题的数据范围从负数开始，因此所有的数据中就存在负负得正的情况，这应该不难想到，因此我们就会有下面的情况：
- 正*正=更大的正数
- 负*负=更大的正数
- 正（负）*负（正）=更小的负数
我们可以很简单的根据数据判断出数据的绝对值只会越乘越大，而对于存在正负两类情况，这就显得很麻烦了，不过只要耐心分析，应该还是没问题的！
Quest3：如何最终实现？
Part1：得到正确思路
我们不能只单单靠一个f数组来实现我们的全部过程，对于负数我们必须拿出额外的部分来处理，我们用g数组记录过程当中的最小值，我们首先可以写出加法的处理过程：
\[\begin{aligned}f[i][j] = max(f[i][j],f[i][k]+f[k+1][j]) \\ \\ g[i][j] = min(g[i][j],g[i][k]+g[k+1][j]) \end{aligned} \]那么对于乘法我们就不得不分类讨论了：
- \(f[i][k]>0,f[k+1][j]>0,g[i][k]>0,g[k+1][j]>0\)
这种情况就很简单，都是正数，那其实\(g\)的操作等同于没有，因为原则上越乘绝对值越大嘛，对于此，我们应该的处理是：
- $ f[i][k]>0.f[k+1][j]>0,g[i][k]>0,g[k+1][j]<0 $
这个时候最小值出现了一个负数，秉承着越乘绝对值越大的原则，能写出下面这个式子：
- $ f[i][k]>0,f[k+1][j]>0,g[i][k]<0,g[k+1][j]<0 $
这种情况和2如出一辙，因此操作上也是一样的：
- $ f[i][k]>0,f[k+1][j]>0,g[i][k]<0,g[k+1][j]<0 $
现在就大为不同了，我们要考虑的，现在乘法所得一定比原先更大且为正数：
为什么要处理\(g\)呢，其实答案显然，我们的\(g\)在这时候可能没有定义出值，也有可能当前所得比原先的值小，越乘绝对值越大指的是所得的积的绝对值比原先两个数的绝对值大。
挖趣，到这里就已经四种情况了，看来又要写好多好长的式子了。。。老实讲，这么算我们得写16个，懒。。所以我们把一正一负的自动归为一类！就像是上面的2,3一样。那这样子我们就写9个，算上那一个多的最多10个，OK！
从头写一遍吧TAT。。
- $ f[i][k],g[i][k],f[k+1][j],g[k+1][j]>0: $
- $ f[i][k],g[i][k],f[k+1][j]>0,g[k+1][j]<0: $
- $ f[i][k],g[i][k]>0,f[k+1][j],g[k+1][j]<0: $
- $ f[i][k],f[k+1][j],g[k+1][j]>0,g[i][k]<0: $
- $ f[i][k],f[k+1][j]>0,g[i][k],g[k+1][j]<0: $
- $ f[i][k]>0,g[i][k],f[k+1][j],g[k+1][j]<0: $
- $ f[k+1][j],g[k+1][j]>0,f[i][k],g[i][k]<0: $
- $ f[k+1][j]>0,f[i][k],g[i][k],g[k+1][j]<0: $
- $ f[i][k],g[i][k],f[k+1][j],g[k+1][j]<0: $
哇呜呜，简直就是史诗级大作
标签：begin,end,Polygon,min,luogu,P4342,max,aligned,dp From： https://www.cnblogs.com/sleepyday/p/18185214