题目

1.和谐宿舍22.合并石子

1.和谐宿舍2

蓝桥杯 算法提高 ADV-298 和谐宿舍2

题目：http://lx.lanqiao.cn/problem.page?gpid=T575

package 练习; import java.util.Scanner; public class _298和谐宿舍2 { public static void main(String[] args) { //输入 Scanner in = new Scanner(System.in); int n,m; n=in.nextInt(); m=in.nextInt(); int high []=new int [n+1]; for (int i=1;i<=n;i++) { high[i]=in.nextInt(); } //求解maxLen[i][j] //maxLen[i][j]表示i到j的作品中最高的高度 //这里的求解方式也用了动态规划，可以通过画表的形式思考。 //求解i到j作品中的最高高度，即可比较i到j-1的最高高度和j的高度 int maxLen[][]=new int [n+1][n+1];//只需填右上角的表 for(int i=1;i<=n;i++) { //初始表，i到i的最高高度为其本身的高度；填斜对角线 maxLen[i][i]=high[i]; } for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { //i到j的高度=MAX(i到j-1的最高高度，j的高度) maxLen[i][j]=Math.max(maxLen[i][j-1], high[j]); } } //dp[i][j]表示前i个作品用j个木板的最小面积和 int dp[][]=new int [n+1][m+1]; //初始化dp for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { dp[i][j]=1000000; } } for(int i=1;i<=n;i++) { //初始化，前i个作品用1个木板时的面积和 dp[i][1]=maxLen[1][i]*i; } //核心思想：前i个作品用j个木板时面积最小，就看前面的作品用j-1个木板时的最小面积+剩余面积 for(int i=2;i<=n;i++) { for(int j=2;j<=m;j++) { if(j>i) continue; for(int k=1;k<=i-1;k++) dp[i][j]=Math.min(dp[i][j], dp[k][j-1]+maxLen[k+1][i]*(i-k)); } } System.out.println(dp[n][m]); } }

对我有帮助的大佬分析：大佬的代码 这是个非常经典的动态规划题目类型，类似于矩阵连乘的思想。

2.合并石子

蓝桥杯 试题 算法提高 合并石子

题目：http://lx.lanqiao.cn/problem.page?gpid=T414

和第一题的思路是一个套路，矩阵连乘的思想

package 练习; import java.util.Scanner; public class _229合并石子_ { public static void main(String[] args) { //输入 Scanner in=new Scanner(System.in); int n=in.nextInt(); int num[]=new int [n+1]; int dp[][]=new int [n+1][n+1]; int sumPre[]=new int [n+1]; sumPre[0]=0; //对dp[i][j]进行初始化 for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { dp[i][j]=(int) 1e+10; } } //合并两大堆的花费=之前合并成两大堆已经用的花费dp[i][j]+这两大堆的重量(sumPre[j]-sumPre[i-1])(因为只能是相邻的两堆合并,所以可以用前缀和) for(int i=1;i<=n;i++) { num[i]=in.nextInt(); sumPre[i]=sumPre[i-1]+num[i]; //前缀和 dp[i][i]=0; //自己和自己是0 } //通过判断乘号的位置来进行dp（？） for (int i=1;i<=n-1;i++) //倒序很妙 { for(int j=i+1;j<=n;j++) { for(int k=i;k<=j-1;k++) { //就是矩阵连乘的思想 dp[i][j]=Math.min(dp[i][j], dp[i][k]+dp[k+1][j]+sumPre[j]-sumPre[i-1]); } } } System.out.print(dp[1][n]); } }