石子合并2——环状合并DP
程序员文章站
2022-09-21 09:09:38
题目描述在一个环形跑道上有N堆石子,每次取相邻两堆进行合并最终合并成为一堆。请问将每次合并后的代价进行累加其总和最少为多少输入第一行为石子堆数N,N<=200第二行到第N行,每行一个正整数代表石子数,其小于10000输出一行,表示最小的总得分样例输入44594输出43此题是典型的合并类DP,板子题,它和石子合并1所不同的是这次的跑道是环状的,也就是首尾相连,最后一个可以和最开始一个合并了。所以我们可以将数组开成双倍的,从而达到环的效果。借此机会...
题目
描述
在一个环形跑道上有N堆石子,每次取相邻两堆进行合并
最终合并成为一堆。请问将每次合并后的代价进行累加
其总和最少为多少
输入
第一行为石子堆数N,N<=200
第二行到第N行,每行一个正整数代表石子数,其小于10000
输出
一行,表示最小的总得分
样例
输入
4
4
5
9
4
输出
43
此题是典型的合并类DP,板子题,它和石子合并1所不同的是这次的跑道是环状的,也就是首尾相连,最后一个可以和最开始一个合并了。
所以我们可以将数组开成双倍的,从而达到环的效果。
借此机会复习一下合并DP的基本思路
可以转化为:
像这样,继续分下去,就会到k=i或j-k可以直接合并的情况了。
参考代码一篇:
#include <bits/stdc++.h>
using namespace std;
int n, a[405], sum[405];
int dp[405][405], ans = 0x3f3f3f3f;;//定义
//dp[i][j]中i表示i-j区间中合并石子的最小花费
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
a[i + n] = a[i];//因为是环状的,所以开双倍数组,输入第一轮数组后,也要给它后面的数组赋值
dp[i][i] = 0;//i-i区间也就是它本身,没有进行和合并,所以花费为0
}
for (int i=1;i<=2*n;++i) {
sum[i] = sum[i - 1] + a[i];//求前缀和
}
for (int k=2;k<=n; ++k) {//枚举区间长度
for (int i=1;i<=2*n-k+1;++i) {//枚举区间起始位置
int j = i + k - 1;//通过长度和起始位置求结束位置
dp[i][j] = 0x3f3f3f3f;//求最小值,所以先给它赋个极大值
for (int t=i;t<j; ++t) {//枚举区间中一个点,当成媒介来递归,转换成求i-t,t+1-j合并+合并花费的子问题
dp[i][j] = min(dp[i][j],dp[i][t]+dp[t+1][j]+sum[j] - sum[i - 1]);
}
}
}
for (int i=1;i<=n;++i) {//比较,因为我们定义了两倍数组,所以去找每一个n的环就是一次完整的合并,求最小值
ans=min(ans,dp[i][i+n-1]);
}
cout << ans;
}
本文地址:https://blog.csdn.net/qq_44635637/article/details/107595579
推荐阅读
-
Python中使用pypdf2合并、分割、加密pdf文件的代码详解
-
Python之利用PyPDF2库实现对PDF的删除和合并
-
c#动态类型,及动态对象的创建,合并2个对象,map实例
-
P1880 [NOI1995]石子合并
-
Python--合并2个字典成1个新字典的9种方法
-
石子合并问题--直线版 HRBUST - 1818
-
荐 opencv进阶学习笔记2:numpy操作图像,色彩空间,查找指定颜色范围,通道分离与合并
-
Python中使用pypdf2合并、分割、加密pdf文件的代码详解
-
石子合并2——环状合并DP
-
Python for Data Analysis v2 | Notes_ Chapter_8 数据规整:聚合、合并和重塑