AcWing 1068. 環形石子合并

題意：

n堆石頭圍成一個圈，然后將相鄰兩堆合并成新的一堆，得分為新的一堆的石頭數
問最高得分合最低得分

題解：

很簡單，區間dp的模板題
和這個題一樣
狀態轉移方程：
dpmax[i][j] = max(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1])
dpmin[i][j]=min(dp[i][k]+dp[k+1][j])+sum[j]-sum[i-1]
因為題目說的是環形，所以數組復制一倍
馬上要java期末考試，所以用java練練

代碼：

import java.io.*; import java.util.*;class Main{static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));static int N = 410, INF = 0X3f3f3f3f;static int[] a = new int[N], sum = new int[N];static int[][] dpMax = new int[N][N];static int[][] dpMin = new int[N][N];public static void main(String[] args) throws Exception{int n = Integer.valueOf(read.readLine());String[] ss = read.readLine().split(" ");for(int i = 1; i <= ss.length; i++){a[i] = Integer.valueOf(ss[i - 1]);a[i + n] = Integer.valueOf(ss[i - 1]);}for(int i = 1; i <= 2 * n; i++){sum[i] = sum[i - 1] + a[i];Arrays.fill(dpMax[i], -INF);Arrays.fill(dpMin[i], INF);}for(int len = 1; len <= n; len++){for(int i = 1; i + len - 1 <= 2 * n; i++){int j = i + len - 1;if(len == 1) {dpMax[i][j] = dpMin[i][j] = 0;}else{for(int k = i; k < j; k++){dpMax[i][j] = Math.max(dpMax[i][j], dpMax[i][k] + dpMax[k + 1][j] + sum[j] - sum[i - 1]);dpMin[i][j] = Math.min(dpMin[i][j], dpMin[i][k] + dpMin[k + 1][j] + sum[j] - sum[i - 1]);}}}}int max = -INF, min = INF;for(int left = 1; left <= n; left++){max = Math.max(max, dpMax[left][left + n - 1]);min = Math.min(min, dpMin[left][left + n - 1]);}System.out.println(min);System.out.println(max);}}

總結

以上是生活随笔為你收集整理的AcWing 1068. 环形石子合并的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。