学步园

4

t -7 t 4 x 2 x 5

33

1 2

由于负负得正，所以你不能只算最大值． 
也就是说要计算多边形上连续的一段所能达到的最小值和最大值．

解题代码：

#include<iostream><br /> using namespace std;<br /> int v[55],min0,max1;<br /> char edge[55];<br /> int m[55][55][2];<br /> void minmax(int n,int i,int j,int s)<br /> {<br /> int e[4],a,b,c,d,r,k;<br /> a=m[i][s][0];b=m[i][s][1];r=(i+s-1)%n+1;c=m[r][j-s][0];d=m[r][j-s][1];<br /> if(edge[(i+s)%n]=='t')<br /> {<br /> min0=a+c;<br /> max1=b+d;<br /> }<br /> else<br /> {<br /> e[0]=a*c;e[1]=a*d;e[2]=b*c;e[3]=b*d;<br /> min0=e[0];max1=e[0];<br /> for(k=1;k<4;k++)<br /> {<br /> if(e[k]<min0)<br /> min0=e[k];<br /> if(e[k]>max1)<br /> max1=e[k];<br /> }<br /> }<br /> }//求对于从顶点i开始，长度为j的链在s处断开的最值<br /> int main()<br /> {<br /> int n,i,j,s,temp,vmax[55],k;<br /> cin>>n;<br /> for(i=1;i<=n;i++)<br /> cin>>edge[i]>>v[i];<br /> for(i=1;i<=n;i++)<br /> m[i][1][0]=m[i][1][1]=v[i];//初始化数组<br /> for(j=2;j<=n;j++)<br /> for(i=1;i<=n;i++)<br /> {<br /> minmax(n,i,j,1);<br /> m[i][j][0]=min0;<br /> m[i][j][1]=max1;//初始化数组<br /> for(s=2;s<j;s++)<br /> {<br /> minmax(n,i,j,s);<br /> if(m[i][j][0]>min0)<br /> m[i][j][0]=min0;<br /> if(m[i][j][1]<max1)<br /> m[i][j][1]=max1;<br /> }//对于每条链的可能的断开位置所得到的最值依次比较求出这条链的最值<br /> }<br /> temp=m[1][n][1];<br /> for(i=2;i<=n;i++)<br /> if(m[i][n][1]>=temp)<br /> temp=m[i][n][1];<br /> k=0;<br /> for(i=1;i<=n;i++)<br /> {<br /> if(m[i][n][1]==temp)<br /> {<br /> vmax[k]=i;<br /> k++;<br /> }<br /> }//依次求出所有将此边删除后能得到最大值的边<br /> printf("%d/n",temp);<br /> for(i=0;i<k-1;i++)<br /> printf("%d ",vmax[i]);<br /> printf("%d/n",vmax[k-1]);<br /> return 0;<br /> }