Mayflyyh
Mayflyyh
MayFlyyh's Blog
bzoj 1233[Usaco2009Open]干草堆tower

1233[Usaco2009Open]干草堆tower

Description

为了调整牛棚顶的电灯的亮度,Bessie必须建一座干草堆使得她能够爬上去够到灯泡 。一共有N大包的干草(1<=N<=100000)(从1到N编号)依靠传送带连续的传输进牛棚来。第i包干草有一个 宽度W_i(1<=w_i<=10000)。所有的干草包的厚度和高度都为1. Bessie必须利用所有N包干草来建立起干草堆,并且按照他们进牛棚的顺序摆放。她可以相放多少包就放 多少包来建立起tower的地基(当然是紧紧的放在一行中)。接下来他可以放置下一个草包放在之前一级 的上方来建立新的一级。注意:每一级不能比下面的一级宽。她持续的这么放置,直到所有的草包都被安 置完成。她必须按顺序堆放,按照草包进入牛棚的顺序。说得更清楚一些:一旦她将一个草包放在第二级 ,她不能将接下来的草包放在地基上。 Bessie的目标是建立起最高的草包堆。

Input
第1行:一个单一的整数N。 第2~N+1行:一个单一的整数:W_i。

Output
第一行:一个单一的整数,表示Bessie可以建立的草包堆的最高高度。

Sample Input
3 1 2 3

Sample Output
2

妙题啊。。可我这个智商水平怎么可能独立做出来呢。。不过看出来从上往下推还是可以的。

据分析,最优解的思路是:每一层尽量短。。也就是同时使得底边最短。即底边最短的,层数一定最高

O(n^2) 做法

设一个F[i]和H[i] 表示包含i块为当前层最后一块的当前层宽度,H[i]表示当前离最高点的距离

外循环跑每个块
内循环j跑(i,n],找一个sum[j-1]-sum[i-1]>=F[j]的且j最小的情况

为什么找sum[j-1]-sum[i-1]>=F[j]?

sum[j-1]-sum[i-1]表示的是[i,j-1],也就是包含i知道j的前块,加起来的长度能否使得j层放在上面,如果可以便满足题目要求。为什么要求j尽量小?感性理解便是在j小的情况下,F[j]可能更长,因为i~j-1包含的草堆更少,所以要求j尽量小。

但O(n^2)是过不去的,有一种用单调队列加速的做法

要求

sum[j-1]-sum[i-1]>=F[j] ①
j>i且j尽量小

堆要求变形:
sum[j-1]-F[j]>=sum[i-1] ②

单调队列优化:
 while(head<tail&&sum[q[head+1]-1]-sum[i-1]>=F[q[head+1]]) head++;

 使其满足①式条件

 因为是倒着推的,所以sum[i-1]在不断减小,也就是说队首的方案必定满足放要求,只不过是不是最优的问题了。如果q[head+1]也满足了话,那必定选q[head+1]而非q[head]

 while(head<=tail&&sum[q[tail]-1]-F[q[tail]]<=sum[i-1]-F[i]) tail--;
 结合②式,如果 q[tail]-1]-F[q[tail]]<=sum[i-1]-F[i]

 那说明当前q[tail]能满足的方案q[i]必定能满足,
 而i肯定比q[tail]好(上文说的j小) 故可以代替掉q[tail]咯

Code


\#include<iostream> #include<cstdio> #include<cstring> #include<string> const int N = 100060; int q[N],head=1,tail=0; int F[N],H[N]; int sum[N],n; int main (){ scanf("%d",&n); for(int i=1;i<=n;++i){ int x; scanf("%d",&x),sum[i]=sum[i-1]+x; } q[++tail]=n+1; for(int i=n;i>=1;--i){ while(head<tail&&sum[q[head+1]-1]-sum[i-1]>=F[q[head+1]]) head++; F[i]=sum[q[head]-1]-sum[i-1]; H[i]=H[q[head]]+1; while(head<=tail&&sum[q[tail]-1]-F[q[tail]]<=sum[i-1]-F[i]) tail--; q[++tail]=i; } printf("%d",H[1]); return 0; }
本文链接:http://www.mayflyyh.com/archives/204
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
首页      DP      bzoj 1233[Usaco2009Open]干草堆tower
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

MayFlyyh's Blog

bzoj 1233[Usaco2009Open]干草堆tower
1233[Usaco2009Open]干草堆tower Description 为了调整牛棚顶的电灯的亮度,Bessie必须建一座干草堆使得她能够爬上去够到灯泡 。一共有N大包的干草(1<=N<=100000)(从1到…
扫描二维码继续阅读
2018-05-16