Java實現 第十一屆藍橋杯——超級膠水（渴望有題目的大佬能給小編提供一下題目，討論群：99979568）
PS：
好久沒寫過演算法題了，總感覺自己寫的思路沒問題，但是結果就是不對，希望哪位大佬有時間能給找找問題
超級膠水
小明有n顆石子，按順序擺成一排，他準備用膠水將這些石子黏在一起。
梅克什字有自己的重量，如果將兩顆石子黏在一起，重量就是兩個石子重量之和
為了粘貼牢固，該題認為兩個石子粘連需要的膠水為兩個石子的重量乘積。
每次只能合併相鄰的兩顆石子，並將合成的石子放在原來的位置，用最少的交水黏在一起，
請幫助小明計算最少需要多少膠水
輸入：
n：石子的數量
n個整數w1，w2……wn，表示每顆石子的重量
輸出：
最少的膠水數量
package 第十一屆藍橋杯; import java.util.Scanner; public class 超級膠水 { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] a = new int[1010]; int[][] temp = new int[1010][1010]; int[][] dp = new int[1010][1010]; int[][] jiaoshui = new int[1010][1010]; // int[][] jiao = new int[1010][1010]; // int[][] zong = new int[1010][1010]; for (int i=1; i<=n; i++) { a[i] = in.nextInt(); temp[i][i] = a[i]; // jiao[i][i]=a[i]; dp[i][i]=a[i]; } for (int i=1; i<n; i++) { for(int j=i+1; j<=n; j++) { temp[i][j] = temp[i][j-1] + a[j]; // jiao[i][j]=jiao[i][j-1]*a[i]; } } for (int r=2; r<=n; r++) { for (int i=1; i<=n-r+1; i++) { int j=i+r-1; jiaoshui[i][j] = Integer.MAX_VALUE; dp[i][j] = Integer.MAX_VALUE; int temp1 = 0; for (int k=i; k<j; k++) { if(jiaoshui[i][j] > dp[i][k] * dp[k+1][j]) temp1=k; dp[i][j] = dp[i][k] + dp[k+1][j]; jiaoshui[i][j] = dp[i][k] * dp[k+1][j]; } jiaoshui[i][j]+=jiaoshui[i][temp1]; jiaoshui[i][j]+=jiaoshui[temp1+1][j]; // dp[i][j] += temp[i][j]; // jiaoshui[i][j]*=jiao[i][j]; } } // System.out.println(dp[1][n]); System.out.println(jiaoshui[1][n]); // System.out.println(zong[1][n]); } }
