Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
线性算法 是怎么来的? 我只能想到RMQ..In Reply To:终于明白怎么做了~~ Posted by:achilles at 2004-11-04 16:12:06 > 用一个一维数组记录‘矩形到当前这一排的高度’,一排一排地读 > 一排一排地处理;在读入地时候,如果是‘F’,h[i]++, 如果是‘R’,h[i]=0 > 然后对当前地 h[maxn] 数组求 最大的矩形面积(应该能理解吧) > 用动态规划可以达到 平均情况下的线性算法 > > 当m排扫描完的时候,结果就出来了 > > 这样的方法,平均情况下是 n^2 的 > > (还要多谢 xiaomi 的提醒~~~ ) Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator