石子合并问题（JAVA版）

- 日理万妓 2023-06-08 06:17 4阅读 0赞

一条直线上摆放着一行共n堆的石子。现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

请编辑计算出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。

Input

输入有多组测试数据。

每组第一行为n(n<=100)，表示有n堆石子，。

二行为n个用空格隔开的整数，依次表示这n堆石子的石子数量ai（0<ai<=100）

Output

每组测试数据输出有一行。输出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。 中间用空格分开。

间用空格分开。

Sample Input

1 2 3

Sample Output

9 11

分析结果：1 和2 合并。1+2=3；第一次合并移动了3次，和3合并。3+3=6，第二次移动了6次，3+6=9；

//最大移动次数
    public static void Maxgroup(int a[]) {
    		int j = 0;
    		int c[][] = new int[a.length][a.length];
    		// 归并长度
    		for (int len = 2; len <= a.length; len++) {
    			for (int i = 1; i < a.length - len + 1; i++) {
    				// i为起点，j为终点
    				j = i + len - 1;
    				if(len==2) {
    					c[i][j]=a[i]+a[j];
    				}else {
    					c[i][j]=Math.max(c[i][j-1]*2+a[j]-c[i][j-2], c[i+1][j]*2+a[i]-c[i+2][j]);
    				}
    			}
    		}
    		for (int i = 0; i < a.length; i++) {
    			for (int e = 0; e < a.length; e++) {
    				System.out.print(c[i][e] + "  ");
    			}
    			System.out.println();
    		}
    	}

思路如下面矩阵

0  0  0  0  
    0  0  3  11  
    0  0  0  5  
    0  0  0  0

//最小移动次数
    public static void Mingroup(int a[]) {
    		int j = 0;
    		int c[][] = new int[a.length][a.length];
    		// 归并长度
    		for (int len = 2; len <= a.length; len++) {
    			for (int i = 1; i < a.length - len + 1; i++) {
    				// i为起点，j为终点
    				j = i + len - 1;
    				if(len==2) {
    					c[i][j]=a[i]+a[j];
    				}else {
    					c[i][j]=Math.min(c[i][j-1]*2+a[j]-c[i][j-2], c[i+1][j]*2+a[i]-c[i+2][j]);
    				}
    			}
    		} 
    		for (int i = 0; i < a.length; i++) {
    			for (int e = 0; e < a.length; e++) {
    				System.out.print(c[i][e] + "  ");
    			}
    			System.out.println();
    		}
    	}

思路如下面矩阵：

0  0  0  0  
    0  0  3  9  
    0  0  0  5  
    0  0  0  0

其实我感觉还是合并的思路，先是2个合并，然后三个，三个合并有不同的通过比较找出最大的或者最小的（先合并1，2或者县合并2，3），以此类推。