因为大区间可以由两个子区间合并得到,所以我们可以用区间dp解决此题
设f[l][r]表示将[l,r]合并成一个点的最大权值
则有$$f[l][r]=max_{l\le k <r} f[l][k]\ op\ f[k+1][r] (op\in \text{{+,*}})$$
很遗憾,这个转移方程是错误的。由于负负得正,两个很小的负数相乘可能会得到一个比两个大正数相乘更大的结果。
那怎么办?
设maxv[l][r]表示将[l,r]合并成一个点的最大权值,minv[l][r]表示将[l,r]合并成一个点的最小权值
这样,枚举断点,最大的maxv[1][n]即为答案,时间复杂度$O(n^4)$
考虑断环为链,讲原串复制一遍并粘到后面,最终$max_{1\le p\le n} maxv[p][p+n-1]$即为答案
时间复杂度$O(n^3)$
这里的转移就比较复杂了,可见代码
//Wan Hong 3.0
//home
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
typedef std::pair<ll,ll> pll;
typedef std::string str;
#define INF (1ll<<58)
ll read()
{
ll f=1,x=0;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
ll max(ll a,ll b)
{
return a>b?a:b;
}
ll min(ll a,ll b)
{
return a<b?a:b;
}
bool umax(ll& a,ll b)
{
if(b>a)return a=b,1;
return 0;
}
bool umin(ll& a,ll b)
{
if(b<a)return a=b,1;
return 0;
}
/**********/
#define MAXN 211
ll maxv[MAXN][MAXN],minv[MAXN][MAXN],a[MAXN],op[MAXN];
int main()
{
ll n=read();
memset(maxv,0xcf,sizeof maxv);memset(minv,0x3f,sizeof minv);
for(ll i=1;i<=n;++i)
{
char c=getchar();
while(c!='t'&&c!='x')c=getchar();
if(c=='t')op[i+n]=op[i]=0;//读入&断环为链
else op[i+n]=op[i]=1;
a[i+n]=a[i]=read();
maxv[i+n][i+n]=minv[i+n][i+n]=maxv[i][i]=minv[i][i]=a[i];
}
for(ll len=2;len<=n;++len)//最长区间长度为n
for(ll l=1;l<=n*2;++l)
{
ll r=l+len-1;
if(r>n*2)break;
//printf("l=%lld r=%lld:",l,r);//debug语句
ll *p=&maxv[l][r];//适度指针怡情
for(ll k=l;k<r;++k)
if(op[k+1])umax(*p,max(maxv[l][k]*maxv[k+1][r],minv[l][k]*minv[k+1][r]));
else umax(*p,maxv[l][k]+maxv[k+1][r]);
//printf("max=%lld ",*p);
p=&minv[l][r];
for(ll k=l;k<r;++k)
if(op[k+1])umin(*p,min(minv[l][k]*minv[k+1][r],min(minv[l][k]*maxv[k+1][r],maxv[l][k]*minv[k+1][r])));
else umin(*p,minv[l][k]+minv[k+1][r]);
//printf("min=%lld\n",*p);
}
ll ans=-INF;
for(ll i=1;i<=n;++i)
umax(ans,maxv[i][n+i-1]);
printf("%lld\n",ans);
for(ll i=1;i<=n;++i)
if(maxv[i][n+i-1]==ans)printf("%lld ",i);
return 0;
}