AC日记——石子归并 codevs 1048

时间:2022-01-15 23:40:24

1048 石子归并

 时间限制: 1 s
 空间限制: 128000 KB
 题目等级 : 黄金 Gold
 查看运行结果
 
 
题目描述 Description

有n堆石子排成一列,每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子,一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序,能够使得总合并代价达到最小。

输入描述 Input Description

第一行一个整数n(n<=100)

第二行n个整数w1,w2...wn  (wi <= 100)

输出描述 Output Description

一个整数表示最小合并代价

样例输入 Sample Input

4

4 1 1 4

样例输出 Sample Output

18

数据范围及提示 Data Size & Hint
 
 
 
思路:
  区间dp(其实就是暴力枚举(毕竟这题数据太水(没办法(>.<))));
 
 
来,上代码:
#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的更多相关文章

  1. AC日记——石子归并 51nod 1021

    石子归并 思路: 经典动态规划——归并类问题: 我们把状态划为n个,即1-n的n个长度为n个状态: 那么,每个长度为i的状态都可以由i-1个长度为i-1的状态推出: 所以,dp转移方程: dp[i][ ...

  2. 1048 石子归并codevs

    1048 石子归并codevs 题目描述 Description 有n堆石子排成一列,每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子,一次合并的代价为两堆石子的重量和w[i]+w[i+1 ...

  3. AC日记——约瑟夫问题 codevs 1282

    1282 约瑟夫问题  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 大师 Master 题解  查看运行结果     题目描述 Description 有编号从1到N的N个小 ...

  4. AC日记——丑数 codevs 1246

    1246 丑数 USACO  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果     题目描述 Description 对于一给定的素 ...

  5. AC日记——砍树 codevs 1388

    1388 砍树  时间限制: 1 s  空间限制: 256000 KB  题目等级 : 黄金 Gold 题解  查看运行结果     题目描述 Description 伐木工人米尔科需要砍倒M米长的木 ...

  6. AC日记——元素查找 codevs 1230

    1230 元素查找  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果     题目描述 Description 给出n个正整数,然后有 ...

  7. AC日记——搞笑世界杯 codevs 1060&lpar;dp&rpar;

    题目描述 Description 随着世界杯小组赛的结束,法国,阿根廷等世界强队都纷纷被淘汰,让人心痛不已. 于是有 人组织了一场搞笑世界杯,将这些被淘汰的强队重新组织起来和世界杯一同比赛.你和你的朋 ...

  8. AC日记——产生数 codevs 1009 (弗洛伊德)(组合数学)

    1009 产生数 2002年NOIP全国联赛普及组  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解  查看运行结果     题目描述 Descriptio ...

  9. AC日记——平衡树练习 codevs 4244

    4244 平衡树练习 思路: 有节操的人不用set也不用map: 代码: #include <cstdio> #include <cstring> #include <i ...

随机推荐

  1. JavaScript语言精粹(读书笔记)

    第一章 精华 1,JavaScript的函数(主要)基于词法作用域(lexical scoping)的*对象.强类型语言允许编译器在编译时检测错误,但弱类型很*,无需建立复杂的类层次,不用做强制造 ...

  2. 如何配置Eclipse&plus;Tomcat 开发环境【转】

                                                                                                        ...

  3. &lbrace;matlab&rcub;取二值图像centroid几种方法性能比较

    试验很简单,取二值图像的质心,三种方法做比较 1.完全采用矩阵性能不做任何循环操作,对find后的值进行除法与取余操作,从而得到centroid 2.完全采用循环操作,最简单明了 3.结合1,2,对每 ...

  4. 后台接受ajax传递值的实例代码

    后台接受ajax传递值的实例代码: 使用ajax可以实现无刷新数据交互,下面是一段后台代码接收ajax传递值的实例代码供需要的朋友参考,希望能够带来帮助. ajax代码如下: $(function ( ...

  5. CentOS 命令随笔

     linux下敲命令时:快速删除当前行已经敲的命令: CTR+U  或者 CTR+/                         快速删除当前行刚输入接近鼠标当前位置的单词:CTR+W 以上在XS ...

  6. JDBC--手动开启Connection事务

    三层架构中的业务逻辑层是处理业务逻辑的部分,很多时候需要调用多步Dao层的增删改操作,这就涉及到使用事务保证数据的一致性. Connection接口自带的事务机制需要保证多步SQL操作使用相同的连接对 ...

  7. HandlerThread实现数字时钟

    1.描述 刚看完Android多线程编程,对HandlerThread比较感兴趣,趁热巩固练习,实现一个了数字时钟,希望对学习HandlerThread有所帮助.如下: 启动一个HandlerThre ...

  8. ASP&period;NET Core的身份认证框架IdentityServer4(4)- 支持的规范

    IdentityServer实现以下规范: OpenID Connect OpenID Connect Core 1.0 (spec) OpenID Connect Discovery 1.0 (sp ...

  9. 2018-2019-2 20165336 《网络对抗技术》 Exp6 信息搜集与漏洞扫描

    2018-2019-2 20165336 <网络对抗技术> Exp6 信息搜集与漏洞扫描 一.原理与实践说明 1.实践内容 本实践的目标是掌握信息搜集的最基础技能.具体有: 各种搜索技巧的 ...

  10. (11)学习笔记 ) ASP&period;NET CORE微服务 Micro-Service ---- Thrift高效通讯 (完结)

    一. 什么是 RPC Restful 采用 Http 进行通讯,优点是开放.标准.简单.兼容性升级容易: 缺点是性能略低.在 QPS 高或者对响应时间要求苛刻的服务上,可以用 RPC(Remote P ...