Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

线性算法 是怎么来的? 我只能想到RMQ..

Posted by yiyiyi4321 at 2007-06-06 14:48:12 on Problem 1964
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator