随笔-38  评论-23  文章-0  trackbacks-0

题目意思如下:
对于给定多边形,N个顶点,N条边。每条边表示一个‘+’或者‘*’,每个顶点是个数值.
在删除一条边的情况下可进行以下操作:
.选择一条边和该边的两个顶点。通过边上的符号计算合并这两个顶点为一个顶点。直到没有边的可选择时.游戏结束。则最后会得到一个顶点的值
题目的意思 让你求出再删除哪一条边的情况,并且通过合理选择边得到一个最大值。

假设 R(i,j)表示从第i个结点开始,顺时针方向连续j个顶点的某个子链,可以考虑该链最后通过中间某条边合成为一个顶点.令 i<=s<=i+j 从R(i,s) 和R(s+1,j)这两个子链通过边(s,s+1)合成为一个顶点

m1为R(i,s)这个子链的结果 a为R(i,s)这个子链的最小结果,b为为R(i,s)这个子链的最大结果,则a<=m1<=b.
m2为R(s+1,j)这个子链的结果.c为R(s+1,j)的这个子链的最小结果,d为R(s+1,j)的这个子链的最大结果,则c<=m2<=d

如果边(s,s+1)为符号‘+’时候 R(i,j)的最大值应该为(b+d)
如果边(s,s+1)为符号‘*’时候R(i,j)的最大值应该为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}


 

posted on 2009-03-30 16:57 米游 阅读(325) 评论(0)  编辑 收藏 引用 所属分类: ACM

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理