学步园

import java.util.Scanner;
public class Main {
   
	public static float p[],q[],c[][],w[][],root[][];
	public static float max=Float.MAX_VALUE;
	public static void bestsolution(float root[][],int i,int j)
	{
		if(i<=j)
		{
			System.out.println("start at: "+i+" ends with: "+j+" root is:"+(int)root[i][j]);
			bestsolution(root, i, (int)root[i][j]-1);
			bestsolution(root, (int)root[i][j]+1, j);
		}
	}
	public static void optimal_choose(float c[][],float root[][],float w[][],int n)
	{
		 int i=0,j=0;
		 for(i = 1;i<=n+1;i++)  
	     {  
	           c[i][i-1] = 0;  
	           w[i][i-1] = q[i-1];  
	     }
		
		 for(int l = 1;l<=n;l++)  
         {  
                 for(i = 1;i<=n-l+1;i++)  
                 {  
                        j = i+l-1;  
                        c[i][j] = max;  
                        w[i][j] = w[i][j-1] + p[j]+q[j];  
                        for(int r = i;r<=j;r++)  
                        {  
                        	     float t = 0;  
                                 t = c[i][r-1]+c[r+1][j] + w[i][j];  
                                 if(t<=c[i][j])  
                                 {  
                                        c[i][j]= t;  
                                        root[i][j] = r;  
                                 }  
                         }  
  
                 }  
        }  
	}
	public static void main(String[] args) {
     Scanner scanner =new Scanner(System.in);
     System.out.println("请输入测试数据的组数：");
     int tests=scanner.nextInt();
     while(tests--!=0)
     {
    	 System.out.println("请输入实节点个数：");
    	 int number=scanner.nextInt();
    	 p=new float[number+1];
    	 System.out.println("请输入每个实节点对应的概率：");
    	 p[0]=0;
    	 for(int i=1;i<=number;i++)
    	 {
    		 p[i]=scanner.nextFloat();
    	 }
    
    	 q=new float[number+1];
    	 System.out.println("请输入每个虚节点对应的概率：");
    	 for(int j=0;j<=number;j++)
    	 {
    		 q[j]=scanner.nextFloat();
    	 }
    	 
    	 c=new float[number+2][number+2];
    	 w=new float[number+2][number+2];
    	 root=new float[number+2][number+2];
    	 
    	 optimal_choose(c,root,w,number);
    	 /*for(int k=0;k<=number;k++)
    	 {
    		 for(int w=0;w<=number;w++)
    		 {
    			 System.out.print(c[k][w]+" ");
    		 }
    		 System.out.println();
    	 }*/
    	 System.out.println(c[1][number]);
         System.out.println("请输出最优决策：");
         bestsolution(root, 1, number);

     }
	}

}