NYOJ 737DP
2024-10-14 23:56:58
石子合并(一)
时间限制:1000 ms | 内存限制:65535 KB
难度:3
- 描述
- 有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 - 来源
- 经典问题
- 上传者
- TC_胡仁东
- 代码:
-
//思路就是从小区间扩大到大区间,最初两个数合并然后区间扩大1就是3个数合并,但因为3个的包含了
//2个的子区间,因此还是合并2个数,再扩大1就是4个数合并........
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int inf=0x7fffffff;
int n,a[],sum[],dp[][];
int main()
{
while(scanf("%d",&n)==){
sum[]=;
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
sum[i]=sum[i-]+a[i];
dp[i][i]=;
}
for(int i=;i<=n;i++){
for(int j=i-;j>=;j--){
dp[j][i]=inf;
for(int k=j;k<i;k++){
dp[j][i]=min(dp[j][i],dp[j][k]+dp[k+][i]+sum[i]-sum[j-]);
}
}
}
printf("%d\n",dp[][n]);
}
return ;
}
最新文章
- 浅谈JavaScript中forEach与each
- Linux文件与目录管理之ls的使用
- GitHub使用教程for VS2012
- (转)HTML特殊字符
- PHP扩展开发(1)-创建基础框架
- shrio初体验(1)
- JavaWeb学习之三层架构实例(二)
- 后台CRUD管理jqGrid 插件下载、使用、demo演示
- windows eclipse安装lombok插件
- ubuntu apt 软件源的更改
- C++中多维数组传递参数
- twindows下omcat8安装后,不能启动服务
- [LTR] RankLib.jar 包介绍
- leecode第八十九题(格雷编码)
- cocos2d-x学习记录6——自定义Button
- django的mysql设置和mysql服务器闲置时间设置
- python编程之禅
- NTP同步网络时间
- D题:数学题(贪心+二分)
- 自动生成makefile
热门文章
- Window下部署MySql数据库
- 应用Response.Write实现带有进度条的多文件上传
- HDU 2490 Parade(DPの单调队列)(2008 Asia Regional Beijing)
- POJ 3714 Raid(计算几何の最近点对)
- php性能优化--opcache
- 并查集(Union/Find)模板及详解
- bootstrap使用中遇到的坑
- iOS-开发过程中应用间跳转问题
- Vue自定义事件,$on(eventName) 监听事件,$emit(eventName) 触发事件
- 3dContactPointAnnotationTool开发日志(二三)