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

O(N)做法

Posted by foreverlin at 2009-06-14 01:37:20 on Problem 2373 and last updated at 2009-06-14 01:47:36
//给定一个区间[1,L],里面有n个区间,现在要求用长度[2a,2b]范围的木板去覆盖,且是完美覆盖(长度确定,轴心自然也确定了)
//其中n个区间很特殊,每个区间不能由超过1个木块覆盖,求最少要几块,注意特殊区间可能重复 
//用区间[1,L]来表示阶段性,dp[i]表示前i个点被覆盖的最优值
//刚才提到了重复,故首先把这些区间合并,这里采取自然合并(注意这里取开区间,为了后面计算决策点),
//用一个bool数组,每读入一个区间就进行覆盖
//这里注意到L是偶数,木块长度也是偶数,也就是说奇数点的状态可以不作考虑 
//接下来就是状态的转移 
//dp[i]=min(dp[j]+1),j+t=i;易知i-j=t;2a<=t<=2b;故i-2b<=j<=i-2a 但是这样的复杂度高达10^9,故继续优化
//考虑其中两个决策点j,k,j<k,若dp[k]>=dp[j]显然k永远都比j决策好,那么j可以剔除掉这样状态i的关键点所构成的序列
//严格单调增,这个可以再队尾维护,队首进行坐标合法范围的维护,总体时间复杂度O(L); 这个和3017思想有点类似 
//由于L为偶数,木板长度也为偶数,还有use[i]=1的连续区间必然被木板覆盖,故这些都跳过只存储可能的关键点,在队列末尾保留非法状态
//但此时的状态i不会更新,也就是说当前是非法状态 

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