GarsiaWachs算法
解决石子问题:
题目描述如下:
有n堆石子排成一列,每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子,一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序,能够使得总合并代价达到最小。(题目可以参见:http://www.wikioi.com/problem/1048/)
算法思想:
设一个序列是A[0..n-1],每次寻找最小的一个满足A[k-1]<=A[k+1]的k,(方便起见设A[-1]和A[n]等于正无穷大)
那么我们就把A[k]与A[k-1]合并,之后找最大的一个满足A[j]>A[k]+A[k-1]的j,把合并后的值A[k]+A[k-1]插入A[j]的后面。(从后往前找,最坏情况为插在头结点的前面)
使用双向链表实现: 实现代码:https://github.com/fox1987/tianticode/blob/master/1048_garsiawatch.cc
该题也可使用使用dp来实现。为区间dp
公式为:Dp[i][j] = min(Dp[i][k] +Dp[k+1][j] + sum[j] –sum[i-1]){i<=k <j}
实现代码:https://github.com/fox1987/tianticode/blob/master/1048_dp.cc
同时需要注意的是该题使用贪心不能得到最优解。即局部最优不一定为全局最优:
一个case为:6 4 2 1 3 5 7 使用贪心得到的解为:76, 而最优解为74
贪心代码:https://github.com/fox1987/tianticode/blob/master/1048_tanxin.cc
refer:http://blog.sina.com.cn/s/blog_a825ada90101no1m.html
最新文章
- compass reset和layout [Sass和compass学习笔记]
- 我是服务的执政官-服务发现和注册工具consul简介
- Android Studio 初使用
- 解决vs2013使用Git推送到远程仓库报错的问题
- 【C语言学习】-04 一维数组、字符数组
- mapred和mapreduce
- oracle存储过程学习---包的概念
- CSS中设置margin:0 auto; 水平居中无效的原因分析
- webpack3新特性介绍
- 0.搭建myeclipse开发环境
- amaze UI 如何添加原生表单验证
- ElasticSearch日常使用脚本
- JS隐藏号码中间4位
- Asp.Net Core 发布异常 502.5 [The Application process failed to Start]
- Web API的参数、多版本和Filter
- latex去掉页眉
- 类的静态(Static)成员——字段
- Oracle ORA-12541:TNS:无监听程序
- 支持Android 的几款开源3D引擎调研
- PHP MySQL -处理语句
热门文章
- SpringCloud-技术专区-Zuul-使用指南
- @Validated和@Valid区别:Spring validation验证框架对入参实体进行嵌套验证必须在相应属性(字段)加上@Valid而不是@Validated
- wrong mechandise category
- svn - Subversion 命令行客户端工具
- 【javascript闭包】转载一篇不错的解释,也有几个大牛的链接
- spring中bean的高级属性之list, set, map以及props元素(含举例)
- spring 结合 redis 例子 (转)
- 防火墙---CentOS
- Linux直接在通过终端打开图片文件
- leetcood学习笔记-9