原题链接:沙子合并
参考代码:
import java.util.Scanner; /** * @author 小张 * {@code @date} 2025/10/2 * 沙子合并 */ public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] arr = new int[n]; // 前缀和 int[] sum = new int[n + 1]; // 打表记录 int[][] dp = new int[n][n]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dp[i][j] = -1; for (int i = 1; i <= n; i++) { arr[i - 1] = scanner.nextInt(); sum[i] = sum[i - 1] + arr[i - 1]; } System.out.println(f(arr , 0 , n - 1 , sum , dp)); } private static int f(int[] arr, int l, int r , int[] sum , int[][] dp) { if (dp[l][r] != -1) return dp[l][r]; if (l == r) { // 不需要合并 返回代价 0 dp[l][r] = 0; return dp[l][r]; } if (l == r - 1) { dp[l][r] = arr[r] + arr[l]; return dp[l][r]; } int minNum = Integer.MAX_VALUE; for (int k = l; k < r; k++) { // 合并左侧的最小代价 int left = f(arr, l, k, sum , dp); // 合并右侧的最小代价 int right = f(arr , k + 1 , r , sum ,dp); // 取左侧和右侧的最小代价和 minNum = Math.min(minNum , left + right); } // 左右两侧最小代价和 + 合并这两侧石子的代价 dp[l][r] = minNum + sum[r + 1] - sum[l]; return dp[l][r]; } }
0.0分
0 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复