作业帮线段覆盖 怎么DP 我是pascal就是用最少的线段,来覆盖 一段区间 比如说 a[i]是线段起点 b[i]是线段终点 for i:=1 to nd ofor j:=1 to i do if a[i]>=b[j] then f[i]=min(f[j]+1) 是这样吗 输入是 n（表示线段数）后
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/06 14:32:23
![线段覆盖 怎么DP 我是pascal就是用最少的线段,来覆盖 一段区间 比如说 a[i]是线段起点 b[i]是线段终点 for i:=1 to nd ofor j:=1 to i do if a[i]>=b[j] then f[i]=min(f[j]+1) 是这样吗 输入是 n（表示线段数）后](/uploads/image/z/15257129-41-9.jpg?t=%E7%BA%BF%E6%AE%B5%E8%A6%86%E7%9B%96+%E6%80%8E%E4%B9%88DP+%E6%88%91%E6%98%AFpascal%E5%B0%B1%E6%98%AF%E7%94%A8%E6%9C%80%E5%B0%91%E7%9A%84%E7%BA%BF%E6%AE%B5%2C%E6%9D%A5%E8%A6%86%E7%9B%96+%E4%B8%80%E6%AE%B5%E5%8C%BA%E9%97%B4+%E6%AF%94%E5%A6%82%E8%AF%B4+a%5Bi%5D%E6%98%AF%E7%BA%BF%E6%AE%B5%E8%B5%B7%E7%82%B9+b%5Bi%5D%E6%98%AF%E7%BA%BF%E6%AE%B5%E7%BB%88%E7%82%B9+for+i%3A%3D1+to+nd+ofor+j%3A%3D1+to+i+do+if+a%5Bi%5D%3E%3Db%5Bj%5D+then+f%5Bi%5D%3Dmin%28f%5Bj%5D%2B1%29+%E6%98%AF%E8%BF%99%E6%A0%B7%E5%90%97+%E8%BE%93%E5%85%A5%E6%98%AF+n%EF%BC%88%E8%A1%A8%E7%A4%BA%E7%BA%BF%E6%AE%B5%E6%95%B0%EF%BC%89%E5%90%8E)
线段覆盖 怎么DP 我是pascal就是用最少的线段,来覆盖 一段区间 比如说 a[i]是线段起点 b[i]是线段终点 for i:=1 to nd ofor j:=1 to i do if a[i]>=b[j] then f[i]=min(f[j]+1) 是这样吗 输入是 n（表示线段数）后
线段覆盖 怎么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】
.
求能覆盖这段区间最少的线段数
线段覆盖 怎么DP 我是pascal就是用最少的线段,来覆盖 一段区间 比如说 a[i]是线段起点 b[i]是线段终点 for i:=1 to nd ofor j:=1 to i do if a[i]>=b[j] then f[i]=min(f[j]+1) 是这样吗 输入是 n（表示线段数）后
这道题应该是使用贪心算法吧.
先以起始位置排序线段,然后
比如现在已经覆盖了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;
覆盖了所有的区间.