題目意思如下:
對于給定多邊形，N個頂點，N條邊。每條邊表示一個‘+’或者‘*’,每個頂點是個數(shù)值.
在刪除一條邊的情況下可進行以下操作：
.選擇一條邊和該邊的兩個頂點。通過邊上的符號計算合并這兩個頂點為一個頂點。直到?jīng)]有邊的可選擇時.游戲結(jié)束。則最后會得到一個頂點的值
題目的意思 讓你求出再刪除哪一條邊的情況，并且通過合理選擇邊得到一個最大值。

假設(shè) R(i,j)表示從第i個結(jié)點開始，順時針方向連續(xù)j個頂點的某個子鏈,可以考慮該鏈最后通過中間某條邊合成為一個頂點.令 i<=s<=i+j 從R(i,s) 和R(s+1,j)這兩個子鏈通過邊(s,s+1)合成為一個頂點
令
m1為R(i,s)這個子鏈的結(jié)果 a為R(i,s)這個子鏈的最小結(jié)果，b為為R(i,s)這個子鏈的最大結(jié)果，則a<=m1<=b.
m2為R(s+1,j)這個子鏈的結(jié)果.c為R(s+1,j)的這個子鏈的最小結(jié)果,d為R(s+1,j)的這個子鏈的最大結(jié)果,則c<=m2<=d
故
如果邊(s,s+1)為符號‘+’時候 R(i,j)的最大值應(yīng)該為(b+d)
如果邊(s,s+1)為符號‘*’時候R(i,j)的最大值應(yīng)該為max(ac,ad,bc,bd) 
//需要一正一負的情況..(a,b)=(-8,-5),(c,d)=(5,8)

 1#include<iostream>
 2#include<algorithm>
 3using namespace std;
 4int v[52],R[52][52][2],n;
 5char ed[52];
 6int getMaxr(int vec,int len,int flag) //flag=0 表示求最小值,flag=1表示求最大值
 7{
 8    int Lmax,Rmax,Lmin,Rmin;
 9    if(len==0)
10        return v[vec];
11    if(len==1)
12    {
13        if(ed[vec%n+1]=='t')
14            R[vec][len][flag]=v[vec]+v[vec%n+1];
15        else
16            R[vec][len][flag]=v[vec]*v[vec%n+1];
17        return R[vec][len][flag];
18    }
19    if(R[vec][len][flag]>-32769&&R[vec][len][flag]<32769)
20        return R[vec][len][flag];
21    for(int i=1;i<=len;i++)
22    {
23        Lmax=getMaxr(vec,i-1,1);
24        Rmax=getMaxr((vec+i-1)%n+1,len-i,1);
25        Lmin=getMaxr(vec,i-1,0);
26        Rmin=getMaxr((vec+i-1)%n+1,len-i,0);
27    //    cout<<Lmax<<" "<<Rmax<<" "<<Lmin<<" "<<Rmin<<endl;
28        if(ed[((vec+i-1)%n+1)]=='t')
29        {
30            if(flag&&R[vec][len][flag]<Lmax+Rmax)
31                R[vec][len][flag]=Lmax+Rmax;
32            if(!flag&&R[vec][len][flag]>Lmin+Rmin)
33                R[vec][len][flag]=Lmin+Rmin;
34        }
35        else
36        {
37            int temp1=max(max(Lmax*Rmin,Lmax*Rmax),max(Lmin*Rmin,Lmin*Rmax));
38            int temp2=min(min(Lmax*Rmin,Lmax*Rmax),min(Lmin*Rmin,Lmin*Rmax));
39            if(flag&&R[vec][len][flag]<temp1)
40                R[vec][len][flag]=temp1;
41            if(!flag&&R[vec][len][flag]>temp2)
42                R[vec][len][flag]=temp2;
43        }
44        //cout<<i<<":"<<R[vec][len][flag]<<endl;
45    }
46    return R[vec][len][flag];
47}
48int main()
49{
50    int flag,re[52],Maxx;
51    while(cin>>n)
52    {
53        Maxx=-32769;
54        flag=0;
55        for(int i=1;i<=n;i++)
56        {
57            getchar();
58            cin>>ed[i]>>v[i];
59        }
60        for(int i=0;i<=n;i++)
61            for(int j=0;j<=n;j++)
62            {
63                R[i][j][0]=32769;
64                R[i][j][1]=-32769;
65            }
66        for(int i=1;i<=n;i++)
67        {
68            re[i]=getMaxr(i,n-1,1);
69            if(re[i]>Maxx)
70                Maxx=re[i];
71        }
72        printf("%d\n",Maxx);
73        for(int i=1;i<=n;i++)
74        {
75            if(Maxx==re[i])
76                if(flag==0)
77                    flag++,cout<<i;
78                else
79                    cout<<" "<<i;
80        }
81        cout<<endl;
82    }
83}