本文共 1856 字，大约阅读时间需要 6 分钟。
题意抽象出数学模型就是说“最少需要多少个区间能完全覆盖整个区间[1,n]”。
一开始没看到“ subsequence of the given sequence” ，直接排序，然后二分查找，居然1A。。充满了奇迹。
AC后百度题解发现自己看错题也能AC，相当自豪！
dp[i]表示覆盖[1,i]最少需要的区间数。
那么对于某段区间[a,b],dp[b]=min(dp[a....b-1])+1;
更新只需更新一点，不用一段。
还有几个细节
//#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair pii;#define pb(a) push(a)#define INF 0x1f1f1f1f#define lson idx<<1,l,mid#define rson idx<<1|1,mid+1,r#define PI 3.1415926535898template T min(const T& a,const T& b,const T& c) { return min(min(a,b),min(a,c));}template T max(const T& a,const T& b,const T& c) { return max(max(a,b),max(a,c));}void debug() {#ifdef ONLINE_JUDGE#else freopen("d:\\in1.txt","r",stdin); freopen("d:\\out1.txt","w",stdout);#endif}int getch() { int ch; while((ch=getchar())!=EOF) { if(ch!=' '&&ch!='\n')return ch; } return EOF;}const int maxn=50005;int n,m;int dp[maxn<<2];int minv[maxn<<2];struct Sorter{ int i,j; bool operator < (const Sorter &ant) const { if(j!=ant.j)return j >1; build(lson); build(rson); PushUp(idx); return 0;}int update(int idx,int l,int r,int pos,int v){ if(l==r) { minv[idx]=min(minv[idx],v); return 0; } int mid=(r+l)>>1; if(pos<=mid)update(lson,pos,v); else update(rson,pos,v); PushUp(idx); return 0;}int query(int idx,int l,int r,int tl,int tr){ if(tl<=l&&tr>=r) return minv[idx]; int mid=(r+l)>>1; int res=INF; if(tl<=mid) res=min(res,query(lson,tl,tr)); if(tr>mid) res=min(res,query(rson,tl,tr)); return res;}int main(){ while(scanf("%d%d",&n,&m)!=EOF) { for(int i=0;i
转载于:https://www.cnblogs.com/BMan/p/3596767.html
