做技术网站赚钱/新公司如何做推广

3229: [Sdoi2008]石子合并

时间限制: 3 Sec  内存限制: 128 MB

提交: 497  解决: 240

[提交][][]

题目描述

在一个操场上摆放着一排N堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

试设计一个算法，计算出将N堆石子合并成一堆的最小得分。

输入

第一行是一个数N。

以下N行每行一个数A，表示石子数目。

输出

共一个数，即N堆石子合并成一堆的最小得分。

样例输入

4

1

1

1

1

样例输出

8

提示

对于 100% 的数据，1≤N≤40000

对于 100% 的数据，1≤A≤200

接下来是嘴巴时间！！

po1：

显然如果数据范围变小这可是一道DP入门题：f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum(i,j)) (i,j表示的是区间[i,j]的最优解，i<=k

O(N^3)!

po2:

为了降低复杂度

介绍四边形优化

设s(i,j)为f[i][j]为最优解时k的值，假设我们已经知道四边形优化是这样的s(i,j-1)<=s(i,j)<=s(i+1,j){我是不会证明的}那么在循环k的时候我们就只用从s(i,j-1)循环到(s+1,j)了，这是近乎于O(1)的。

O(N^2)!! 但是数组无法滚动会卡掉空间QAQ

po3:

GarsiaWachs！

这是专门用于解决石子合并类问题的算法：一个序列是A[0..n-1]，每次寻找最小的一个满足A[k-1]<=A[k+1]的k，(方便起见设A[-1]和A[n]等于正无穷大)那么我们就把A[k]与A[k-1]合并，之后找最大的一个满足A[j]>A[k]+A[k-1]的j,把合并后的值A[k]+A[k-1]插入A[j]的后面，反复进行直到序列为1个数字。

栗子：

186 64 35 32 103  (35<103)

186 67 64 103  (64<103)

186 131 103 　　(A[-1]和A[n]等于正无穷大)

234 186

420

ans=420+234+131+67=852

O(N^2) 可以勉强过了这道题

po4：

在po3的基础上splay维护此序列。

O(NlogN)

#include

#include

#include

#include

#include

#define yyj(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout);

#define llg long long

#define maxn 40010

llg i,j,k,x,n,m,a[maxn],ans;

using namespace std;

llg get()

{

llg i=; char c=getchar();

while(c>''||c

while(c>=''&&c<='')i=i*+c-'',c=getchar();

return i;

}

int main()

{

yyj("a");

cin>>n;

for (i=;i<=n;i++) a[i]=get();

a[]=a[n+]=0x7fffffff;

for (m=;m

{

a[n-m+]=0x7fffffff;

for (k=;k<=n-m+;k++) if (a[k-]<=a[k+]) break;

x=a[k-]+a[k]; ans+=x;

for (i=k-;i<=n-m;i++) a[i]=a[i+];

for (j=k-;j>=;j--) if (a[j]>x) break;

for (i=n-m;i>j+;i--) a[i]=a[i-];

a[j+]=x;

}

cout<

return ;

}

你以为这可以A？这只是一发常数写大了超时的

当你把常数写小

1548112

正确

1484 kb

60 ms

1080 B

2016-07-14 20:13:13

【BZOJ 3229】 3229&colon; &lbrack;Sdoi2008&rsqb;石子合并 (GarsiaWachs算法)

3229: [Sdoi2008]石子合并 Description 在一个操场上摆放着一排N堆石子.现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合 ...

&lbrack;SDOI2008&rsqb;石子合并 题解

题面 GarsiaWachs算法专门解决石子合并问题: 设一个序列是A[0..n-1],每次寻找最小的一个满足A[k-1]<=A[k+1]的k,那么我们就把A[k]与A[k-1]合并,并向前寻找 ...

洛谷 P5569 &lbrack;SDOI2008&rsqb;石子合并 GarsiaWachs算法

石子合并终极通用版 #include using namespace std ; ]; int n,t,ans; void combine(int k) { ...

BZOJ-3229 石子合并 GarsiaWachs算法

经典DP?稳T 3229: [Sdoi2008]石子合并 Time Limit: 3 Sec Memory Limit: 128 MB Submit: 426 Solved: 202 [Submit] ...

BZOJ 3227&colon; &lbrack;Sdoi2008&rsqb;红黑树&lpar;tree&rpar;

BZOJ 3227: [Sdoi2008]红黑树(tree) 标签(空格分隔): OI-BZOJ OI-其它 Time Limit: 10 Sec Memory Limit: 128 MB Descr ...

RQNOJ 490 环形石子合并

题目链接:https://www.rqnoj.cn/problem/490 题目描述 在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆,并将新的一 ...

codevs1048 石子合并

题目链接:http://codevs.cn/problem/1048/ 题目描述 Description 有n堆石子排成一列,每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子,一次合并的代 ...

石子合并&lbrack;DP-N3&rsqb;

题目描述 在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分. 试设计出1个算法,计算出将N堆石子合并成1 ...

51Nod 1021 石子合并 Label：Water DP

N堆石子摆成一条线.现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的代价.计算将N堆石子合并成一堆的最小代价.   例如: 1 2 3 4,有 ...

随机推荐

C&num; 获取时间差状态

/// /// 根据时间获取时间状态 /// ///

读jQuery源码 - Callbacks

代码的本质突出顺序.有序这一概念,尤其在javascript——毕竟javascript是单线程引擎. javascript拥有函数式编程的特性,而又因为javascript单线程引擎,我们的函数总是 ...

你应该知道的25道Javascript面试题

题目来自 25 Essential JavaScript Interview Questions.闲来无事,正好切一下. 一 What is a potential pitfall with usin ...

option对象概念

一.基础理解: var e = document.getElementById("selectId");   e.options = new Option("文本&quo ...

gcc&sol;g&plus;&plus;命令认识

gcc & g++是gnu中最主要和最流行的c & c++编译器 . g++用来针对c++的处理命令,以.cpp为后缀,对于c语言后缀名一般为.c.这时候命令换做gcc即可. 下面以T ...

O-C浮点数转化整数

1.简单粗暴,直接转化 float f = 1.5; int a; a = (int)f; NSLog("a = %d",a); 输出结果是1.(int)是强制类型转化,丢弃浮点数 ...

Thinkpad E430&plus;CentOS 6&period;4&plus; linux-3&period;10&period;12内核网卡驱动(无线&plus;有线)配置

配置并编译安装内核模块和内核后,解压附件 firmware.tar.bz2,拷贝其中的rtlwifi文件夹到/lib/firmware下,然后 执行装载内核模块命令: sudo modprobe rt ...

js颜色转换

很久之前面试遇到过一个题.写个颜色转换的方法. function RGB2Color(r,g,b) { return '#' + byte2Hex(r) + byte2Hex(g) + byte2He ...

vue中提示&dollar;index is not defined

今天学习Vue中遇到了一个报错信息:$index is not defined,是我写了个for循环在HTML中,然后是因为版本的问题 下面是解决方法: 原来的是 v-for="person ...

Windows下Tomcat内存占用过高问题跟踪&lpar;ProcessExplorer&plus;jstack&rpar;

一.问题描述 Tomcat下面部署很多个java项目的war包,tomcat启动一段时间后,发现cpu占用过高,整个界面卡死! 二.通过process explorer查看java进程下的线程 pro ...