Gravatar
HouJikan
积分:1857
提交:596 / 1973
考试我肯定写不出来

Gravatar
C语言入门
积分:572
提交:125 / 374
回复 @digital-T : ORZZZZ

题目 1543 最优挤奶法
2014-03-13 23:54:46
Gravatar
,
积分:425
提交:128 / 305
回复 @digital-T :
orz

题目 1543 最优挤奶法
2014-03-11 18:06:27
Gravatar
digital-T
积分:2213
提交:586 / 1311
回复 @King_Algorithm :
喂喂不要乱封线段树导师啦……我被神犇们solo了怎么办?再说还不是你信手拈来,现在敲线段树比我溜多了= =

题目 1543 最优挤奶法
2014-03-10 14:32:34
Gravatar
超级傲娇的AC酱
积分:646
提交:244 / 660
好多DP都是可以用线段树写的。
一种简单容易看出的DP(可以直接以区间建树)有以下特点:
1.子问题数量少(太多的话会把一个节点建的巨复杂)(这种情况下还是交给cstdio大神来建一些高大上的树)
甚至可以写成O(n)的地推。子问题处理到该问题的状态转移更一般形式的方程就是子节点计算父节点的运算法则。
2.相关子问题不要调用相邻很远的节点的值,譬如石子归并。不过话说区间DP还是可以套线段树的。要不然再套一颗建立与其他节点之间的联系。要不按照子问题建树而非区间。(这是的时间复杂度就不是以区间长度为准的了)
更多的研究还有待寡人继续学习,或咨询@cstdio 和线段树导师@digital-T
不过也不至于又让我用32min的单指敲键盘敲得内存时间压制你们吧

Gravatar
,
积分:425
提交:128 / 305
回复 @cstdio :
太神了,目测省选要被你们虐了

题目 1543 最优挤奶法
2014-03-09 20:13:09
Gravatar
cstdio
积分:4748
提交:1198 / 2108
回复 @Chenyao :
每次12个数取4个怎么大了……

Gravatar
Chenyao2333
积分:770
提交:122 / 365
回复 @cstdio :
觉得常数有些可怕

题目 1543 最优挤奶法
2014-03-09 13:19:12
Gravatar
cstdio
积分:4748
提交:1198 / 2108
回复 @Chenyao :
左开右开,左开右不开,左不开右开,左不开右不开的四个最大值

Gravatar
Chenyao2333
积分:770
提交:122 / 365
这题是用线段树做么?维护i到j产量的最大值,总感觉有些奇怪

题目 1543 最优挤奶法
2014-03-09 00:07:23
Gravatar
digital-T
积分:2213
提交:586 / 1311
输出 "%lld" LL很重要 = v =

题目 1543 最优挤奶法
2014-03-08 17:46:43