sdnu 1045.石子合并1 1048.石子合并2

2024-02-21 00:58
文章标签 合并 石子 1045 1048 sdnu

本文主要是介绍sdnu 1045.石子合并1 1048.石子合并2,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

原题链接:

1045:  http://210.44.14.31/problem/show/1045

1048:  http://210.44.14.31/problem/show/1048



1045:有n堆石子排成一行,每次选择相邻的两堆石子,将其合并为一堆,记录该次合并的得分为两堆石子个数之和。已知每堆石子的石子个数,求当所有石子合并为一堆时,最小的总得分。

设dp[i][j]表示第i到第j堆石子合并的最优值。

那么就有状态转移公式:




代码如下:

#include<iostream>
#include<cstdio>
using namespace std;const int MAX_INT = 1 << 30;
int stone[200 + 5];
int dp[200 + 2][200 + 2];
int sum[200 + 5];				//存1到n堆的石子总数目
int n;int min(int x, int y)
{return x > y ? y : x;
}void GetMin()
{for (int len = 1; len <= n; len++){for (int begin = 1; begin + len <= n; begin++){int end = begin + len;int temp = sum[end] - sum[begin - 1];		//存begin到end堆石子的总数目,也可直接放入min函数中dp[begin][end] = MAX_INT;for (int k = begin; k < end; k++)dp[begin][end] = min(dp[begin][end], dp[begin][k] + dp[k + 1][end] + temp);		//更新dp[begin][end]的值}}return ;
}int main()
{scanf_s("%d", &n);sum[0] = 0;for (int i = 1; i <= n; i++){scanf_s("%d", &stone[i]);sum[i] += stone[i] + sum[i - 1];}GetMin();printf("%d\n",dp[1][n]);return 0;
}

1048:有n堆石子排成一圈,每次选择相邻的两堆石子,将其合并为一堆,记录该次合并的得分为两堆石子个数之和。已知每堆石子的石子个数,求当所有石子合并为一堆时,最小的总得分。

状态转移方程同上,只需解决一下边界问题。


代码如下:

#include<cstdio>
using namespace std;const int MAX_INT = 1 << 30;
int dp[200 + 2][200 + 2];
int sum[200 + 5];
int stone[200 + 5];
int n,MIN;int GetSum(int begin, int end)
{if (end <= n)return sum[end] - sum[begin - 1];return sum[n] - sum[begin - 1] + sum[end%n];}
int min(int x, int y)
{return x > y ? y : x;
}void GetMin()
{for (int len = 1; len <= n; len++){for (int begin = 0; begin <= n; begin++){int end = (begin + len) % n == 0 ? n : (begin + len) % n;int temp = GetSum(begin, begin+len);	//注意传begin+lendp[begin][end] = MAX_INT;for (int k = 0; k < len; k++)dp[begin][end] = min(dp[begin][end], dp[begin][(begin + k) % n == 0 ? n : (begin + k) % n] + dp[(begin + k + 1) % n == 0 ? n : (begin + k + 1) % n][end] + temp);//dp[][0]不使用}}MIN = dp[1][n];for (int i = 2; i <= n;i++)if (MIN > dp[i][i - 1])MIN = dp[i][i - 1];
}int main()
{scanf_s("%d", &n);sum[0] = 0;for (int i = 1; i <= n; i++){scanf_s("%d", &stone[i]);sum[i] += sum[i - 1] + stone[i];}GetMin();printf("%d\n", MIN);return 0;
}





这篇关于sdnu 1045.石子合并1 1048.石子合并2的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/730111

相关文章

Python实现合并与拆分多个PDF文档中的指定页

《Python实现合并与拆分多个PDF文档中的指定页》这篇文章主要为大家详细介绍了如何使用Python实现将多个PDF文档中的指定页合并生成新的PDF以及拆分PDF,感兴趣的小伙伴可以参考一下... 安装所需要的库pip install PyPDF2 -i https://pypi.tuna.tsingh

使用Apache POI在Java中实现Excel单元格的合并

《使用ApachePOI在Java中实现Excel单元格的合并》在日常工作中,Excel是一个不可或缺的工具,尤其是在处理大量数据时,本文将介绍如何使用ApachePOI库在Java中实现Excel... 目录工具类介绍工具类代码调用示例依赖配置总结在日常工作中,Excel 是一个不可或缺的工http://

使用Python创建一个能够筛选文件的PDF合并工具

《使用Python创建一个能够筛选文件的PDF合并工具》这篇文章主要为大家详细介绍了如何使用Python创建一个能够筛选文件的PDF合并工具,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录背景主要功能全部代码代码解析1. 初始化 wx.Frame 窗口2. 创建工具栏3. 创建布局和界面控件4

Python自动化办公之合并多个Excel

《Python自动化办公之合并多个Excel》在日常的办公自动化工作中,尤其是处理大量数据时,合并多个Excel表格是一个常见且繁琐的任务,下面小编就来为大家介绍一下如何使用Python轻松实现合... 目录为什么选择 python 自动化目标使用 Python 合并多个 Excel 文件安装所需库示例代码

使用Python合并 Excel单元格指定行列或单元格范围

《使用Python合并Excel单元格指定行列或单元格范围》合并Excel单元格是Excel数据处理和表格设计中的一项常用操作,本文将介绍如何通过Python合并Excel中的指定行列或单... 目录python Excel库安装Python合并Excel 中的指定行Python合并Excel 中的指定列P

基于C#实现PDF文件合并工具

《基于C#实现PDF文件合并工具》这篇文章主要为大家详细介绍了如何基于C#实现一个简单的PDF文件合并工具,文中的示例代码简洁易懂,有需要的小伙伴可以跟随小编一起学习一下... 界面主要用于发票PDF文件的合并。经常出差要报销的很有用。代码using System;using System.Col

Python视频剪辑合并操作的实现示例

《Python视频剪辑合并操作的实现示例》很多人在创作视频时都需要进行剪辑,本文主要介绍了Python视频剪辑合并操作的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录介绍安装FFmpegWindowsMACOS安装MoviePy剪切视频合并视频转换视频结论介绍

不删数据还能合并磁盘? 让电脑C盘D盘合并并保留数据的技巧

《不删数据还能合并磁盘?让电脑C盘D盘合并并保留数据的技巧》在Windows操作系统中,合并C盘和D盘是一个相对复杂的任务,尤其是当你不希望删除其中的数据时,幸运的是,有几种方法可以实现这一目标且在... 在电脑生产时,制造商常为C盘分配较小的磁盘空间,以确保软件在运行过程中不会出现磁盘空间不足的问题。但在

在C#中合并和解析相对路径方式

《在C#中合并和解析相对路径方式》Path类提供了几个用于操作文件路径的静态方法,其中包括Combine方法和GetFullPath方法,Combine方法将两个路径合并在一起,但不会解析包含相对元素... 目录C#合并和解析相对路径System.IO.Path类幸运的是总结C#合并和解析相对路径对于 C

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que