石子归并问题(nyoj737)
2024-09-20 15:03:43
石子合并(一)
时间限制: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_胡仁东
- 我也不知道为什么要这样做,写着写着就这样了,然后就过了........
- 没有优化的代码:
-
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
#define ll long long
#define _cle(m, a) memset(m, a, sizeof(m))
#define repu(i, a, b) for(int i = a; i < b; i++)
#define repd(i, a, b) for(int i = b; i >= a; i--)
#define sfi(n) scanf("%d", &n)
#define pfi(n) printf("%d\n", n)
#define sfi2(n, m) scanf("%d%d", &n, &m)
#define pfi2(n, m) printf("%d %d\n", n, m)
#define pfi3(a, b, c) printf("%d %d %d\n", a, b, c)
#define MAXN 205
const int INF = 0x3f3f3f3f;
int dp[MAXN][MAXN];
int a[MAXN];
int sum[MAXN];
int main()
{
int n;
while(~sfi(n))
{
_cle(dp, 0x3f);
sum[] = ;
repu(i, , n)
{
sfi(a[i]);
dp[i][i] = ;
sum[i + ] = sum[i] + a[i];
} for(int i = n - ; i >= ; i--)
repu(j, i, n)
{
repu(k, i, j)
dp[i][j] = min(dp[i][j], (dp[i][k] + dp[k + ][j]) + sum[j + ] - sum[i]);
}
pfi(dp[][n - ]);
}
return ;
}
最新文章
- SQL,Linq,Lambda之间的转换练习
- fir.im Weekly - 进击的 Swift
- 直接修改.NET程序集 LLBL Gen 2.x-4.x 许可授权方法研究
- Virtualbox虚拟机安装CentOS6.5图文详细教程
- Nginx 使用IP限制访问来源
- Delphi 7学习开发控件
- jquery如何删除一个元素后面的所有元素
- 数据导出为excel表格
- linux系统下怎么安装.deb文件
- JAVA中的成员变量与局部变量
- 为zend studio增加Extjs代码提示功能
- CentOS7系统下搭建Jenkins环境
- 利用no_merge优化
- Jetty监控线程使用情况的配置
- 201521123054 《Java程序设计》第7周学习总结
- 【学习总结】Git学习-参考廖雪峰老师教程-期末总结
- C# 获取区域和语言值
- 【Linux】-NO.86.Linux.6.C.1.001-【CentOS 7 Install GCC】-
- Node.js概要
- EF5+MVC4系列(10) mvc的布局页面 _ViewStart.Cshtml