多边形——————区间dp

原题链接：https://www.acwing.com/problem/content/285/　　

题意简单来说就是：给你一个环，断掉一条边使其成为一个链，用这个链跑dp，求最大得分。

首先这不是一道板子题。。。跟板子区别如下：

1.多了一重循环，最开始要求断掉一条边，但是我们不知道要断掉哪一条边，因此需要循环一遍来比较。

2.计算方法有加法有乘法，而且数据有正数有负数。这两个条件任意一个都不足惧，但是如果凑在一起。。。就很微妙了。

　　何出此言？比如说，我们用 f [ i ] [ j ]来表示从i号点到j号点的最大得分。那么假如，最后一次的运算是乘法。你在最后一次计算的时候，用于相乘的两个数，肯定都是它们各自那个区间的最优解，也就是最大的。然而，假如说在这个过程中，你淘汰了一些负数的值，那就很危险了。比如，你最后选择了1000和100相乘，但是本来你可以让-10000和-3000相乘的，那不就直接gg了吗。。

　　负负得正，真是麻烦。。。。

　　那怎么解决呢？其实也简单。只要另开一个数组记录最小得分即可~~；

3.题目还要求： 有些边如果在首次移动中被删除，可以导致最高得分。在输出文件的第二行，要求列举出所有这样的边，而且按照升序输出，其间用一个空格分开。（这句话直接粘贴的），也就是说，我们需要用一个数组把每条边和断掉该条边所能获得的最大得分匹配起来，以便最后比较。

说的差不多了，上代码：

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <cstring> 
using namespace std;
const int maxn=50+5,Inf=1e9+10;
int n,data[maxn<<1];//用来存储各点权；因为是环，所以左移一位； 
int f[maxn<<1][maxn<<1][3];// f[i][j][1]表示从i号点到j号点的最大得分，f[i][j][2]表示从***到***的最小得分； 
int ff[maxn<<1];//ff储存每条断边的最大得分，便于最后查找 ； 
char c[maxn<<1]; //储存符号； 
int q,w,e,r;//方便比较的变量。。 
int ans_point=(-1)*Inf;//最大得分,先初始化为最小； 
void Read(){
    cin>>n;//因为有字符+空格的输入。。所以cin比较方便； 
    for(int i=1;i<=n;++i){
        cin>>c[i]>>data[i];
        c[i+n]=c[i];
        data[i+n]=data[i];
    }
}
void Solve(){
    for(int i=1;i<=n;++i){//枚举断边，断边编号+n就是形成的链； 
        for(int j=1;j<=(n<<1);++j){//初始化； 
            for(int k=1;k<=(n<<1);++k){
                f[j][k][1]=(-1)*Inf;//求最大值； 
                f[j][k][2]=Inf;//求最小值； 
            }
        }
        for(int j=1;j<=(n<<1);++j){//初始化区间dp； 
            f[j][j][1]=f[j][j][2]=data[j];
            if(c[j+1]=='t')  f[j][j+1][1]=f[j][j+1][2]=data[j]+data[j+1];
            else f[j][j+1][1]=f[j][j+1][2]=data[j]*data[j+1];
        }
        for(int l=2;l<=n;++l){//枚举区间长度； 
            for(int j=i;j+l<=i+n;++j){//终止条件！！！小心出错；j是起点，k是终点； 
                int k=j+l-1;//把这里的l写成i了，找了半天错。。。吐了吐了； 
                for(int x=j;x<k;++x){//不可以等于k，因为有x+1； 
                    if(c[x+1]=='t'){//读过题的都知道，c[x+1]连接的是x号节点和(x+1)号节点； 
                        f[j][k][1]=max(f[j][k][1],f[j][x][1]+f[x+1][k][1]);
                        f[j][k][2]=min(f[j][k][2],f[j][x][2]+f[x+1][k][2]);
                    }else{
                        q=f[j][x][1]*f[x+1][k][1];
                        w=f[j][x][2]*f[x+1][k][2];
                        e=f[j][x][1]*f[x+1][k][2];
                        r=f[j][x][2]*f[x+1][k][1];
                        f[j][k][1]=max(f[j][k][1],max(max(q,w),max(e,r)));
                        f[j][k][2]=min(f[j][k][2],min(min(q,w),min(e,r)));
                    }
                }
            }
        }
        ff[i]=f[i][i+n-1][1];//注意是i+n-1不是i+n。。小学学的植树问题不要搞错； 
    }
    for(int i=1;i<=n;++i){//因为可能有多个最大边，所以先把最大得分算出来，然后。。 
        ans_point=max(ans_point,ff[i]);
    }
    printf("%d
",ans_point);//注意换行； 
    for(int i=1;i<=n;++i){//然后输出所有跟最大得分相等的边就行了； 
        if(ans_point==ff[i]) printf("%d ",i);//注意空格； 
    }
}
int main(){//芜湖，可怜的主函数，啥也没干； 
    Read();
    Solve();
    return 0;
}