石子合并(区间动态规划)- NYOJ 737

描述

有N堆石子排成一排,每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆,每次合并花费的代价为这两堆石子的和,经过N-1次合并后成为一堆。求出总的代价最小值。

输入

有多组测试数据,输入到文件结束。 每组测试数据第一行有一个整数n,表示有n堆石子。 接下来的一行有n(0< n <200)个数,分别表示这n堆石子的数目,用空格隔开

输出

输出总代价的最小值,占单独的一行

样例输入

3

1 2 3

7

13 7 8 16 21 4 18

样例输出

9

239

思路:

若没有要求将相邻的两堆石子堆成一堆,那么那么我们可以把n堆石子放入一个优先队列,每次取出最小的两堆,合并后压入优先队列,直到队列中只有一堆为止。

题目要求合并的过程只能每次将相邻的两堆石子堆成一堆,所以使用区间动态规划来解决。

即若要求一个大的区间的最优解,先求小区间的最优解,然后小区间慢慢的推出大区间的最优解。

核心部分就是三层for循环,第一层枚举区间的长度,第二层枚举起点的位置,第三层枚举最后一次合并的位置。

例如:

要求1~5这个区间,用dp[1][5]来形容1~5的最优值,那么dp[1][5]肯定为dp[1][1]+dp[2][5],dp[1][2]+dp[3][5], dp[1][3]+dp[4][5] ,d[1][4]+dp[4][5]这个四个值里面最小的一个,而这些子区间肯定是由更小的子区间组成的,所以应该一步一步推,先求小子区间最优解,最后求出dp[1][n]。

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
//#define inf 1<<20
const int maxn = 210;
int n, a[maxn];
int  dp[maxn][maxn];
//dp[i][j]表示从第i堆到第j堆合并的代价
int  sum[maxn][maxn];//表示石头的数量
int main()
{
    ios::sync_with_stdio(0);
    while (cin >> n)
    {
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        memset(sum, 0, sizeof(sum));
        //fill(dp[0],dp[0]+n*n,inf);//错误
        fill(dp[0], dp[0] + maxn * maxn, inf); //fill填充量必须是常数

        for (int i = 1; i <= n; i++)
            sum[i][i] = a[i], dp[i][i] = 0;

        for (int len = 1; len < n; len++) { //区间长度
            for (int i = 1; i <= n && i + len <= n; i++) { //区间起点
                int j = i + len; //区间终点
                for (int k = i; k <= j; k++) //用k来表示分割区间
                {
                    sum[i][j] = sum[i][k] + sum[k + 1][j];
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[i][j]);
                }
            }
        }
        cout << dp[1][n] << endl;
    }
    return 0;
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-05-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程

说说正则表达式的使用

今日分享:正则表达式 一:正则表达式的定义及用途 正则表达式是一种特殊的字符串,字符串中的每个字符都含有特定的意义。使用者通过将正则中不同的字符组合成不同的字符...

1998
来自专栏云时之间

深度学习与神经网络:制作数据集,完成应用(1)

在这一篇文章里,我们将继续上一篇文章的工作,并且在上一篇文章的前提下加入数据集的制作,最终我们将完成这个全连接神经网络的小栗子.

8256
来自专栏Laoqi's Linux运维专列

正则扩展练习

grep命令的-P选项: 最典型的用法是,匹配指定字符串之间的字符。 比如,我们想在一句话(Hello,my name is aming.)中匹配中间的一段字符...

4136
来自专栏Django中文社区

Django 博客文章自动生成摘要的两种方法

首页的博客文章列表通常需要显示摘要,Django 有两种方法来实现这个需求。 复写 save 方法 第一种方法是通过复写模型的 save 方法,从正文字段摘取前...

36610
来自专栏mathor

LeetCode130. 被围绕的区域

 bfs题,主函数中枚举每一个起点,如果是'O'就开始bfs搜索,首先将'O'变为'X',然后将周围是'O'都入队。这里有个地方要注意,如果'O'并不是被...

1002
来自专栏有趣的Python和你

微信好友全头像直接上图代码代码分析

1443
来自专栏互联网杂技

express中app.use和app.get的区别及解析

写在前面:最近研究nodejs及其web框架express,对app.use和app.get没理解清,以致踩了坑浪费不少时间,我根据自己实践及总结出此博客,若有...

3606
来自专栏云时之间

深度学习与神经网络:制作数据集,完成应用(1)

2144
来自专栏数据结构与算法

22:因子分解

22:因子分解 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 输入一个数,输出其素因子分解表达式。 输入输入一个整数...

34112
来自专栏蘑菇先生的技术笔记

算法数据结构(一)-B树

2284

扫码关注云+社区

领取腾讯云代金券