| 题目名称 | 1543. 最优挤奶法 |
|---|---|
| 输入输出 | optmilk.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 11 |
| 题目来源 |
 mouse
于2014-03-07加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：33， 提交：62， 通过率：53.23% | ||||
 vampire |
100 | 0.162 s | 2.76 MiB | C++ |
 Faller |
100 | 0.176 s | 7.18 MiB | C++ |
 rewine |
100 | 0.178 s | 4.13 MiB | C++ |
 sunshine123 |
100 | 0.182 s | 19.39 MiB | C++ |
|
sunshine123 |
100 | 0.182 s | 19.39 MiB | C++ |
|
vampire |
100 | 0.205 s | 2.76 MiB | C++ |
 真呆菌 |
100 | 0.208 s | 2.63 MiB | C++ |
 fye |
100 | 0.216 s | 2.54 MiB | C++ |
|
fye |
100 | 0.218 s | 2.79 MiB | C++ |
 RP++ |
100 | 0.248 s | 2.75 MiB | C++ |
| 本题关联比赛 | |||
| 20140307 | |||
| 关于 最优挤奶法 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
考试我肯定写不出来
| ||||
|
回复 @digital-T : ORZZZZ
 C语言入门
2014-03-13 23:54
10楼
| ||||
|
回复 @digital-T :
orz  ,
2014-03-11 18:06
9楼
| ||||
|
回复 @King_Algorithm :
喂喂不要乱封线段树导师啦……我被神犇们solo了怎么办？再说还不是你信手拈来，现在敲线段树比我溜多了= =  digital-T
2014-03-10 14:32
8楼
| ||||
|
好多DP都是可以用线段树写的。
一种简单容易看出的DP(可以直接以区间建树)有以下特点： 1.子问题数量少(太多的话会把一个节点建的巨复杂)(这种情况下还是交给cstdio大神来建一些高大上的树) 甚至可以写成O(n)的地推。子问题处理到该问题的状态转移更一般形式的方程就是子节点计算父节点的运算法则。 2.相关子问题不要调用相邻很远的节点的值，譬如石子归并。不过话说区间DP还是可以套线段树的。要不然再套一颗建立与其他节点之间的联系。要不按照子问题建树而非区间。(这是的时间复杂度就不是以区间长度为准的了) 更多的研究还有待寡人继续学习  ,或咨询@cstdio 和线段树导师@digital-T 不过也不至于又让我用32min的单指敲键盘敲得内存和时间压制你们吧 | ||||
|
回复 @cstdio :
太神了，目测省选要被你们虐了 ,
2014-03-09 20:13
6楼
| ||||
|
回复 @Chenyao :
每次12个数取4个怎么大了…… | ||||
|
回复 @cstdio :
觉得常数有些可怕  Chenyao2333
2014-03-09 13:19
4楼
| ||||
|
回复 @Chenyao :
左开右开，左开右不开，左不开右开，左不开右不开的四个最大值 | ||||
|
这题是用线段树做么?维护i到j产量的最大值,总感觉有些奇怪
Chenyao2333
2014-03-09 00:07
2楼
| ||||
HouJikan
超级傲娇的AC酱
cstdio【题目描述】
FJ最近新购进了一个牛舍，里面装有N（1<=N<=40,000）台挤奶器，这些挤奶器排成了一行，编号依次为1～N。
第i台挤奶器一天能挤M(i)（1<=M(i)<=100,000）单位的牛奶。不幸的是，由于这些机器挨的太近，所以当某台机器工作的时候，它左右相邻的两台机器就不能开机工作，（两端的两台机器都只有一个相邻的机器），FJ可以自由地决定每天打开哪些台机器。
FJ想知道在连续的D（1<=D<=50,000）天里这些机器的最大产量。在每一天开始的时候，他有充足的时间来对其中一台机器i进行保养从而使其产量从当天开始就升级至一个新的值。现给你一份每日的改造清单，请你告诉FJ这D天的最大产量和，注意，结果可能会超出32位二进制所能表示的范围。
【输入格式】
第1行为N和D；
接下来有N行，其中第i行为M(i)的初始值；
再接下来有D行，其中第i行有两个整数k和m,表示FJ在第i天会把第k台机器的产量升级至m。
【输出格式】
输出只有一行，即D天的最大产量和。
【样例输入】
5 3 1 2 3 4 5 5 2 2 7 1 10
【样例输出】
32
【提示】
输出解释：
第1天，最优产量为2+4=6（或1+3+2=6），第二天，最优产量为7+4=11，第3天的最优产量为10+3+2=15。
【来源】
在此键入。