fac3_5.java

java 算法设计与分析的好资料.由王晓东先生主编.

//本程序取自王晓东编著“算法分析与设计”第 81 页，例
//多边形游戏动态规划解法
public class Fac3_5{
   static int [][][]m;
   int []v;
   static char []op;
   static int minf,maxf;
   static int n;
     public Fac3_5(char op1[],int m1[][][],int v1[],int n1)
  {
    op=op1;
    m=m1;
    v=v1;
    n=n1;
  }
   public static void minMax(int i,int s,int j)
   {
     int []e=new int[5];
     int 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];
         if(op[r]=='+'){
          minf=a+c;
          maxf=b+d;
           }
          else
           {
           e[1]=a*c;
           e[2]=a*d;
           e[3]=b*c;
           e[4]=b*d;
           minf=e[1];
           maxf=e[1];
           for(int k=2;k<5;k++){
             if(minf>e[k])minf=e[k];
             if(maxf<e[k])maxf=e[k];
             }
            }
           }
           
  public static int polyMax()
  { 
    for(int j=2;j<=n;j++)
      for(int i=1;i<=n;i++)
       for(int s=1;s<j;s++){
        minMax(i,s,j);
        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;
  }

  public static void main(String args[])
  {
  //注意，由于程序中都是基于数组下标1的，而JAVA 数组从0开始
  // 使用前在V1和OP1的第一个位置增加标识位0和@，才能得出正确结果
    int v1[]={0,5,6,1,3,2,4};
    char op1[]={'@','+','*','+','*','*','+'};
    int  n1=v1.length-1;
    int [][][]m1=new int[n1+1][n1+1][2];
    for(int i=1;i<=n1;i++){
     m1[i][1][0]=v1[i];
     m1[i][1][1]=v1[i];
    }
    Fac3_5 abc=new Fac3_5(op1,m1,v1,n1);
    System.out.println("最大值是"+polyMax());
  }
}