[蓝桥杯][算法提高 ADV-229]合并石子(java)(动态规划)九十分,思路正确,超时
算法提高 合并石子
时间限制:2.0s 内存限制:256.0MB
问题描述
在一条直线上有n堆石子,每堆有一定的数量,每次可以将两堆相邻的石子合并,合并后放在两堆的中间位置,合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。
输入格式
输入第一行包含一个整数n,表示石子的堆数。
接下来一行,包含n个整数,按顺序给出每堆石子的大小 。
输出格式
输出一个整数,表示合并的最小花费。
样例输入
5
1 2 3 4 5
样例输出
33
数据规模和约定
1<=n<=1000, 每堆石子至少1颗,最多10000颗。
反思错误:
①一开始是用递归解题,结果第三题就超时,,,,Java是真的慢……看来以后适当用用C/C++了。
②写递归的时候,一定要注意结束条件!!!不一定只有一种结束条件!!!!仔细想想。
③然后改成三个循环嵌套,最后一个超时。
解题思路:
首先输出特殊的情况,本题没有零,有个一,首先判断n==1,输入一个值后,直接输出0;
两个也可以算特殊情况,我就不写了。
合并成一堆石子-------分解一下:两堆合并成一堆,---------再分解:四堆合并成两堆
如果你想到了递归,那很好,下边就很好理解了。
int[][] dp;
先写出动态方程:dp[i][j]=Math.min(dp[i][j], dp[i][k]+dp[k+1][j]+sum[i][j])
其中是说,从 i 堆石子 到 j 堆石子的最小合并数,k就是上边说的分解( i 到 k 为一堆,k+1到 j 为一堆),sum[i][j]表示 i 到 j 石子总和。
for(int j=1;j<=n;++j)
for(int i=j-1;i>0;--i)
for(int k=i;k<j;++k)
这是循环的结构,看看是不是能更好理解。。。
还是看代码吧,总觉的自己说的不清楚。。代码清晰。
Java代码:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n=cin.nextInt();
if(n==1) {cin.nextInt();System.out.println(0);return;}
int[][] dp = new int[n+1][n+1];
int[] sum = new int[n+1];
for(int ni=1;ni<=n;++ni) {
sum[ni]=sum[ni-1]+cin.nextInt();
}
for(int j=1;j<=n;++j) {
for(int i=j-1;i>0;--i) {
dp[i][j]=999999999;
for(int k=i;k<j;++k)
dp[i][j]=Math.min(dp[i][j], dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
}
}
System.out.println(dp[1][n]);
cin.close();
}
}
结果截图: