网站建设感悟,自己做的网站怎么赚钱,网站导读怎么做,查网站是不是用shopify做的问题描述在一条直线上有n堆石子#xff0c;每堆有一定的数量#xff0c;每次可以将两堆相邻的石子合并#xff0c;合并后放在两堆的中间位置#xff0c;合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。输入格式输入第一行包含一个整数n#xff0c;表示石…问题描述 在一条直线上有n堆石子每堆有一定的数量每次可以将两堆相邻的石子合并合并后放在两堆的中间位置合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。 输入格式 输入第一行包含一个整数n表示石子的堆数。 接下来一行包含n个整数按顺序给出每堆石子的大小 。 输出格式 输出一个整数表示合并的最小花费。 样例输入 51 2 3 4 5 样例输出 33 数据规模和约定 1n1000, 每堆石子至少1颗最多10000颗。 题目分析 这是一道很经典的动态规划题据说但是我不会哈哈哈。我的理解是逆向考虑这个题把一堆石头分为两堆。 因此设置一个中间点k d[ i ][ j ] min(d[ i ][ n ], d[ 1 ][ k ] d[k 1][ j ])遍历每一个处于[ i , j ]中的每一个中间点k 递归实现的话最后一个样例会超时。 int dp(int i, int j) {if (d[i][j] || ij) return d[i][j];int mi bigdata;for (int ii i; ii j; ii) {int t dp(i, ii) dp(ii 1, j);if(mi t) mi t;}return d[i][j] mi sum[j] - sum[i - 1];
} 循环实现 for (int i n - 1; i 0; i--) {//起点for (int j i 1; j n; j) {//终点long long t bigdata;for (int k i; k j; k) {//中间点long long temp d[i][k] d[k 1][j];if (t temp) t temp;}d[i][j] t sum[j] - sum[i - 1];}} 转载于:https://www.cnblogs.com/woxiaosade/p/10455677.html
