题目大意&＃xff1a;给一个长度为n的区间&＃xff0c;m条线段序列&＃xff0c;找出这个序列的一个最短子序列&＃xff0c;使得区间完全被覆盖。
题目分析&＃xff1a;这道题不难想&＃xff0c;定义状态dp(i)表示用前 i 条线段覆盖区间1~第 i 线段的右端点需要的最少数目&＃xff0c;状态转移方程为dp(i)&＃61;min(dp(j))&＃43;1。其中第 j 条线段与第 i 条线段有交集。很显然&＃xff0c;这个状态转移方程跟LIS问题的状态转移方程几乎一样&＃xff0c;时间复杂度为O(m*m)。起初&＃xff0c;我想套用LIS问题的O(nlogn)的那种解法&＃xff0c;得到两个WA之后才感觉到很难套用成功&＃xff0c;理论上完全没问题&＃xff0c;但实现起来很困难。之后查了题解才知道&＃xff0c;是用线段树优化的。
代码如下&＃xff1a;
# include
# include
# include
# include
using namespace std;const int N&＃61;50005;
const int INF&＃61;1000000000;int n,m;
int tr[N*4];void build(int rt,int l,int r)
{tr[rt]&＃61;INF;if(l&＃61;&＃61;r) return ;build(rt<<1,l,(l&＃43;r)/2);build(rt<<1|1,(l&＃43;r)/2&＃43;1,r);
}void update(int pos,int rt,int val,int l,int r)
{if(tr[rt]>val) tr[rt]&＃61;val;if(l&＃61;&＃61;r) return ;int m&＃61;(l&＃43;r)>>1;if(pos<&＃61;m) update(pos,rt<<1,val,l,m);else update(pos,rt<<1|1,val,m&＃43;1,r);
}int query(int rt,int L,int R,int l,int r)
{if(L<&＃61;l&&r<&＃61;R) return tr[rt];int m&＃61;(l&＃43;r)>>1;if(R<&＃61;m) return query(rt<<1,L,R,l,m);else if(L>m) return query(rt<<1|1,L,R,m&＃43;1,r);else return min(query(rt<<1,L,R,l,m),query(rt<<1|1,L,R,m&＃43;1,r));
}int main()
{int a,b,T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);build(1,1,n);update(1,1,0,1,n);while(m--){scanf("%d%d",&a,&b);int x&＃61;query(1,a,b,1,n);update(b,1,x&＃43;1,1,n);}printf("%d\n",query(1,n,n,1,n));if(T) printf("\n");}return 0;
}
京公网安备 11010802041100号