暑假acwing算法总结32:区间DP
2021/8/2 12:05:56
本文主要是介绍暑假acwing算法总结32:区间DP,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
-
2、类似Huffman树的石子合并
- Huffman树是所有任意两堆石子可以任意合并,但是该DP问题只能合并相邻的两堆,所以用区间DP
- 按照区间长度遍历,先遍历两堆的最小值显然是所有相邻两堆相加,遍历三堆及以上时就要考虑那种更优,通过从l~r-1划线的方式找最优的解,前提是前面的状态已经被计算过
- 像1 3 5
- 前面的状态f(1,2)=4,f(2,3)=8
- 所以在1~2划线f(1,3)=min(f(1,1)+f(2,3),f(1,2)+f(3,3))
- 同理最终状态f(1,n)就是最小值
- 代码
#include<iostream> using namespace std; const int N=310; int f[N][N]; int a[N]; int main() { int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) a[i]+=a[i-1]; for(int len=2;len<=n;len++) { for(int i=1;i+len-1<=n;i++) { int l=i,r=i+len-1; f[l][r]=2e9; for(int k=l;k<r;k++) f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+a[r]-a[l-1]); } } cout<<f[1][n]<<endl; return 0; }
-
2021-08-02写于商丘
这篇关于暑假acwing算法总结32:区间DP的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-21拼接的xml报文,尖括号都被转移成了< 是什么原因-icode9专业技术文章分享
- 2024-09-21Svg Sprite Icon教程:从入门到实践
- 2024-09-21Svg Sprite Icon实战:从入门到上手
- 2024-09-20构建一个多PDF RAG聊天机器人:使用Langchain和Streamlit及代码
- 2024-09-20whatsapp webhook 回调的签名验证偶尔会失败是什么原因-icode9专业技术文章分享
- 2024-09-19Excel数据导出课程:初学者必备教程
- 2024-09-19Excel数据导入课程:新手入门指南
- 2024-09-19RBAC的权限管理入门教程
- 2024-09-19如何使用Svg Sprite Icon制作图标
- 2024-09-19uniapp 如何实现点赞后全局更新数据-icode9专业技术文章分享