//给定一个区间[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不会更新，也就是说当前是非法状态 

• 还是写成O(L)比较好 (620) 20053565 2010-12-27 22:41:39
  • Re:还是写成O(L)比较好 (2620) QWEDSA 2012-05-26 21:28:28