#include<iostream>
using namespace std;
int m[100][100][100];
char op[100];//运算符
int v[100];//顶点数值
void minmax(int n,int i,int s,int j,int& minf,int& maxf,int m[100][100][100],char op[100])//????????????????????
{
int e[4];
int a=m[i][s][0],b=m[i][s][1];
int r=(i+s-1)%n+1,c=m[r][j-s][0],d=m[r][j-s][1];
if(op[r]==‘t‘)
{
minf=a+c;
maxf=b+d;
}
else
{
e[1]=a*c;
//此链最后一次合并运算在op[i+s]处发生(1<=s<=j-1),则可在op[i+s]处将链分割成两个
//子链,p(i,s),p(i+s,j-s),设m1是对子链 p(i,s)的任意一种合并方式得到的值，而a,b分别是在所有可能的合并
//中得到的最小值和最大值，同理对m2,c,d;依此定义，a<=m1<=b,c<=m2<=d;
//由于子链 p(i,s),p(i+s,j-s)的方式决定了 p(i,s)在op[i+s]处断开后的合并方式，在 op[i+s]处合并后其值为
//m=(m1)op[i+s](m2)
//满足最优子结构性质，主链的最大值 最小值由子链的最大值最小值得到，由主链最优性可推出子链最优性
e[2]=a*d;
e[3]=b*c;
e[4]=b*d;
minf=e[1];maxf=e[1];
for(int r=2;r<5;r++)
{
if(minf>e[r])minf=e[r];
if(maxf<e[r])maxf=e[r];
}
}
}
int polymax(int n)
{
int minf,maxf;
for(int j=2;j<=n;j++)
{
for(int i=1;i<=n;i++)
{
for(int s=1;s<j;s++)
{
minmax(n,i,s,j,minf,maxf,m,op);
if(m[i][j][0]>minf)m[i][j][0]=minf;
if(m[i][j][1]<maxf)m[i][j][1]=maxf;
}
}
}
int temp=m[1][n][1];
for(int i=2;i<=n;i++)
if(temp<m[i][n][1])temp=m[i][n][1];
return temp;
}
int main()
{
int n;//顶点个数
while(cin>>n)
{
for(int i=1;i<=n;i++)
{
cin>>v[i]>>op[i];
}
cout<<polymax(n)<<endl;
}
}
*/多边形游戏问题,布布扣,bubuko.com
多边形游戏问题
原文：http://blog.csdn.net/u013240812/article/details/23214239
