實際上就是枚舉所有區(qū)間，求出所有區(qū)間可以獲得的最大值和最小值，區(qū)間L的的結(jié)果可以由區(qū)間L-1的結(jié)果組合得到。
這題有一個小技巧很好用，就是求第i個結(jié)點順時針向后的第t個結(jié)點如果是node(i,t)的話，那么node (i,t+1)的標(biāo)號可以由
((i+t)%n )+1得到，實際上lebel[node(i,t)]=((i+t-1)%n )+1;所以這題結(jié)點從1開始存似乎更加便于計算。
//coded by abilitytao
//2010年6月1日17:25:38
#include <iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=100;
int n;
int fmax[maxn][maxn];
int fmin[maxn][maxn];
int v[maxn];
int op[maxn];
void init()//初始化
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
fmax[i][j]=-999999999;
fmin[i][j]=999999999;
}
for(int i=1;i<=n;i++)
fmax[i][0]=fmin[i][0]=v[i];
}
void input()
{
scanf("%d",&n);
cin.ignore();
int i;
for(i=1;i<=n;i++)
{
char tem[10];
scanf("%s",tem);
if(tem[0]=='t')
op[i]=0;//0代表+號
else
op[i]=1;//1代表乘號
scanf("%d",&v[i]);
}
}
void solve()//DP過程
{
int mm=-999999999;
int i,t,L;
for(L=1;L<=n-1;L++)
{
for(i=1;i<=n;i++)
{
for(t=0;t<=L-1;t++)
{
if(op[(i+t)%n+1]==0)
{
fmin[i][L]=min(fmin[i][L],fmin[i][t]+fmin[(i+t)%n+1][L-t-1]);
fmax[i][L]=max(fmax[i][L],fmax[i][t]+fmax[(i+t)%n+1][L-t-1]);
}
else
{
fmin[i][L]=min(fmin[i][L],fmin[i][t]*fmin[(i+t)%n+1][L-t-1]);
fmin[i][L]=min(fmin[i][L],fmin[i][t]*fmax[(i+t)%n+1][L-t-1]);
fmin[i][L]=min(fmin[i][L],fmax[i][t]*fmin[(i+t)%n+1][L-t-1]);
fmin[i][L]=min(fmin[i][L],fmax[i][t]*fmax[(i+t)%n+1][L-t-1]);
fmax[i][L]=max(fmax[i][L],fmin[i][t]*fmin[(i+t)%n+1][L-t-1]);
fmax[i][L]=max(fmax[i][L],fmin[i][t]*fmax[(i+t)%n+1][L-t-1]);
fmax[i][L]=max(fmax[i][L],fmax[i][t]*fmin[(i+t)%n+1][L-t-1]);
fmax[i][L]=max(fmax[i][L],fmax[i][t]*fmax[(i+t)%n+1][L-t-1]);
}
}
}
}
for(i=1;i<=n;i++)
if(fmax[i][n-1]>mm)
mm=fmax[i][n-1];
printf("%d\n",mm);
for(i=1;i<=n;i++)
if(fmax[i][n-1]==mm)
printf("%d ",i);
printf("\n");
}
int main()
{
input();
init();
solve();
return 0;
}