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

• Re:还是写成O(L)比较好 (2620) QWEDSA 2012-05-26 21:28:28