大师作文网线段覆盖 怎么DP 我是pascal
来源：学生作业帮 编辑：大师作文网作业帮 分类：综合作业 时间：2024/11/14 20:02:27
线段覆盖 怎么DP 我是pascal
就是用最少的线段,来覆盖 一段区间 比如说 a[i]是线段起点 b[i]是线段终点
for i:=1 to nd o
for j:=1 to i do
if a[i]>=b[j] then f[i]=min(f[j]+1) 是这样吗
输入是
n（表示线段数）后面n行
a[i] b[i]
a[i+1] b[i+1】
.
求能覆盖这段区间最少的线段数
就是用最少的线段,来覆盖 一段区间 比如说 a[i]是线段起点 b[i]是线段终点
for i:=1 to nd o
for j:=1 to i do
if a[i]>=b[j] then f[i]=min(f[j]+1) 是这样吗
输入是
n（表示线段数）后面n行
a[i] b[i]
a[i+1] b[i+1】
.
求能覆盖这段区间最少的线段数
这道题应该是使用贪心算法吧.
先以起始位置排序线段,然后
比如现在已经覆盖了x的区间.
寻找以1~x-1为开始的区间里能向下扩展最多的线段.
实际上不需要每次都寻找1~x-1.中间用过一个线段,前面的都是无用的.因此只需要一个变量记录查到哪里就行了
O（n）算法
大概是这样（伪代码）s线段开始e线段结束
sort(以s[i]为关键字,s[i],e[i])
p=0;
ed=0;
tmp=0;
ans=0;
while edn then 无法覆盖所有区间
if s[p]>ed then 无法覆盖所有区间
tmp:=min(tmp,e[p])
if (p+1)>n or s[p+1]>ed then
begin
inc(ans);ed:=tmp;
end
end;
覆盖了所有的区间.
先以起始位置排序线段,然后
比如现在已经覆盖了x的区间.
寻找以1~x-1为开始的区间里能向下扩展最多的线段.
实际上不需要每次都寻找1~x-1.中间用过一个线段,前面的都是无用的.因此只需要一个变量记录查到哪里就行了
O（n）算法
大概是这样（伪代码）s线段开始e线段结束
sort(以s[i]为关键字,s[i],e[i])
p=0;
ed=0;
tmp=0;
ans=0;
while edn then 无法覆盖所有区间
if s[p]>ed then 无法覆盖所有区间
tmp:=min(tmp,e[p])
if (p+1)>n or s[p+1]>ed then
begin
inc(ans);ed:=tmp;
end
end;
覆盖了所有的区间.