/**//*
多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。
游戏第1步，将一条边删除。
随后n-1步按以下方式操作：
（1） 选择一条边E以及由E连接着的两个顶点V1和V2；
（2） 用一个新的顶点取代边E以及由E连接着的两个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。
最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。
问题：对于给定的多边形，计算最高得分。
该问题是动态规划中的一个典型问题，具体解法如下：
*/
public class PloyMax
{
int minf;
int maxf;
public int Min_Max(int n,int i,int j,int s,char[] op,int[][][] m)
{
int[] e=new int[4];
int a=m[i][s][0];
int b=m[i][s][1];
int r=(i+s)%n;
int c=m[r][j-s][0];
int d=m[r][j-s][1];
if(op[r]=='+')
{
this.minf=a+c;
this.maxf=b+d;
}
else
{
e[0]=a*c;
e[1]=a*d;
e[2]=b*c;
e[3]=b*d;
minf=e[0];
maxf=e[0];
for(int k=1;k<4;k++)
{
if(minf>e[k])minf=e[k];
if(maxf<e[k])maxf=e[k];
}
}
return r;
}
public int Ploy_Max(int n,char[] op,int[][][] m)
{
int[][][] b=new int[n][n+1][2];
for(int j=2;j<=n;j++)
for(int i=0;i<n;i++)
for(int s=1;s<j;s++)
{
int c=Min_Max(n,i,j,s,op,m);
if(m[i][j][0]>minf||m[i][j][0]==0)
{
m[i][j][0]=minf;
}
if(m[i][j][1]<maxf||m[i][j][1]==0)
{
m[i][j][1]=maxf;
b[i][j][0]=s;
b[i][j][1]=c;
}
}
int temp=m[0][n][1];
int position=0;
for(int k=1;k<n;k++)
{
if(temp<m[k][n][1])
{
temp=m[k][n][1];
position=k;
}
}
traceBack(position,n,m,b);
return temp;
}
public void traceBack(int i,int n,int[][][]m,int[][][] b)
{
if(n==1){
return;
}
traceBack(i,b[i][n][0],m,b);
traceBack((i+b[i][n][0])%n,n-b[i][n][0],m,b);
System.out.println(b[i][n][1]+"");
}
public static void main(String[] args)
{
char []op={'+','*','*','+'};
int []a={2,8,-3,7};
int[][][] m=new int[a.length][a.length+1][2];
for(int i=0;i<a.length;i++)
for(int j=0;j<=a.length;j++)
{
m[i][j][0]=0;
m[i][j][1]=0;
}
for(int i=0;i<a.length;i++)
{
m[i][1][0]=a[i];
m[i][1][1]=a[i];
}
PloyMax pm=new PloyMax();
int max=pm.Ploy_Max(a.length,op,m);
System.out.println(max);
}
}
posted on 2008-06-30 17:32
夏日清风 阅读(602)
评论(0) 编辑 收藏 所属分类:
算法