有n堆石子排成一列,每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子,一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序,能够使得总合并代价达到最小。
第一行一个整数n(n<=100)
第二行n个整数w1,w2...wn (wi <= 100)
一个整数表示最小合并代价
4
4 1 1 4
18
#include<cstdio>
#include<cstring>
#include<algorithm> using namespace std; int n,dp[][][],sum[]; int main()
{
scanf("%d",&n);
memset(dp,/,sizeof(dp));
for(int i=;i<=n;i++)
{
scanf("%d",&dp[][i][i]);
sum[i]=sum[i-]+dp[][i][i];
dp[][i][i]=;
}
for(int i=;i<n;i++){for(int j=;j<=n;j++) dp[i][j][j]=dp[][j][j];}
for(int i=;i<n;i++)
{
for(int j=;j<=n;j++)
{
for(int r=j;r<=n;r++)
{
dp[i][j][r]=min(dp[i][j][r],dp[i-][j][r]);
for(int v=j;v<r;v++)
{
dp[i][j][r]=min(dp[i][j][r],dp[i-][j][v]+dp[i-][v+][r]+sum[r]-sum[j-]);
}
}
}
}
printf("%d\n",dp[n-][][n]);
return ;
}
AC日记——石子归并 codevs 1048的更多相关文章
-
AC日记——石子归并 51nod 1021
石子归并 思路: 经典动态规划——归并类问题: 我们把状态划为n个,即1-n的n个长度为n个状态: 那么,每个长度为i的状态都可以由i-1个长度为i-1的状态推出: 所以,dp转移方程: dp[i][ ...
-
1048 石子归并codevs
1048 石子归并codevs 题目描述 Description 有n堆石子排成一列,每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子,一次合并的代价为两堆石子的重量和w[i]+w[i+1 ...
-
AC日记——约瑟夫问题 codevs 1282
1282 约瑟夫问题 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 大师 Master 题解 查看运行结果 题目描述 Description 有编号从1到N的N个小 ...
-
AC日记——丑数 codevs 1246
1246 丑数 USACO 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题解 查看运行结果 题目描述 Description 对于一给定的素 ...
-
AC日记——砍树 codevs 1388
1388 砍树 时间限制: 1 s 空间限制: 256000 KB 题目等级 : 黄金 Gold 题解 查看运行结果 题目描述 Description 伐木工人米尔科需要砍倒M米长的木 ...
-
AC日记——元素查找 codevs 1230
1230 元素查找 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题解 查看运行结果 题目描述 Description 给出n个正整数,然后有 ...
-
AC日记——搞笑世界杯 codevs 1060(dp)
题目描述 Description 随着世界杯小组赛的结束,法国,阿根廷等世界强队都纷纷被淘汰,让人心痛不已. 于是有 人组织了一场搞笑世界杯,将这些被淘汰的强队重新组织起来和世界杯一同比赛.你和你的朋 ...
-
AC日记——产生数 codevs 1009 (弗洛伊德)(组合数学)
1009 产生数 2002年NOIP全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题解 查看运行结果 题目描述 Descriptio ...
-
AC日记——平衡树练习 codevs 4244
4244 平衡树练习 思路: 有节操的人不用set也不用map: 代码: #include <cstdio> #include <cstring> #include <i ...
随机推荐
-
JavaScript语言精粹(读书笔记)
第一章 精华 1,JavaScript的函数(主要)基于词法作用域(lexical scoping)的*对象.强类型语言允许编译器在编译时检测错误,但弱类型很*,无需建立复杂的类层次,不用做强制造 ...
-
如何配置Eclipse+Tomcat 开发环境【转】
...
-
{matlab}取二值图像centroid几种方法性能比较
试验很简单,取二值图像的质心,三种方法做比较 1.完全采用矩阵性能不做任何循环操作,对find后的值进行除法与取余操作,从而得到centroid 2.完全采用循环操作,最简单明了 3.结合1,2,对每 ...
-
后台接受ajax传递值的实例代码
后台接受ajax传递值的实例代码: 使用ajax可以实现无刷新数据交互,下面是一段后台代码接收ajax传递值的实例代码供需要的朋友参考,希望能够带来帮助. ajax代码如下: $(function ( ...
-
CentOS 命令随笔
linux下敲命令时:快速删除当前行已经敲的命令: CTR+U 或者 CTR+/ 快速删除当前行刚输入接近鼠标当前位置的单词:CTR+W 以上在XS ...
-
JDBC--手动开启Connection事务
三层架构中的业务逻辑层是处理业务逻辑的部分,很多时候需要调用多步Dao层的增删改操作,这就涉及到使用事务保证数据的一致性. Connection接口自带的事务机制需要保证多步SQL操作使用相同的连接对 ...
-
HandlerThread实现数字时钟
1.描述 刚看完Android多线程编程,对HandlerThread比较感兴趣,趁热巩固练习,实现一个了数字时钟,希望对学习HandlerThread有所帮助.如下: 启动一个HandlerThre ...
-
ASP.NET Core的身份认证框架IdentityServer4(4)- 支持的规范
IdentityServer实现以下规范: OpenID Connect OpenID Connect Core 1.0 (spec) OpenID Connect Discovery 1.0 (sp ...
-
2018-2019-2 20165336 《网络对抗技术》 Exp6 信息搜集与漏洞扫描
2018-2019-2 20165336 <网络对抗技术> Exp6 信息搜集与漏洞扫描 一.原理与实践说明 1.实践内容 本实践的目标是掌握信息搜集的最基础技能.具体有: 各种搜索技巧的 ...
-
(11)学习笔记 ) ASP.NET CORE微服务 Micro-Service ---- Thrift高效通讯 (完结)
一. 什么是 RPC Restful 采用 Http 进行通讯,优点是开放.标准.简单.兼容性升级容易: 缺点是性能略低.在 QPS 高或者对响应时间要求苛刻的服务上,可以用 RPC(Remote P ...