題目鏈接：點擊查看
題目大意：給出一個長度為 n 的序列，現(xiàn)在要求分成盡可能少的子段，且每個子段需要滿足：
最大值與最小值的差值小于等于 s子段長度大于等于 l
題目分析：dp[ i ] 代表的是前 i 個數(shù)字分成最少的子段個數(shù)，轉(zhuǎn)移方程如下：
dp[ i ] = dp[ j - 1 ] + 1：第 i 項單獨一段dp[ i ] = dp[ j - 2 ] + 1：第 i 項與 i - 1 項組成一段...dp[ i ] = dp[ 0 ] + 1：第 1 ~ i 項組成一段
顯然是取上面合法的前驅(qū)的最小值用來維護(hù) dp[ i ]，因為需要滿足條件一，又因為子串的長度與 delta ，也就是最大值與最小值的差，成反比，所以可以二分找到 dp[ j ] 的左端點 l，而 dp[ j ] 的右端點 r 同時也被條件二限制，此時的問題就轉(zhuǎn)換成了求區(qū)間 [ l , r ] 內(nèi) dp 的最小值了，這里用線段樹維護(hù)一下就好，總的來說需要維護(hù)兩個線段樹，因為維護(hù) dp[ i ] 的過程中需要套上一個二分，所以總的時間復(fù)雜度為 O( nlog^2n )
代碼：
?
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;namespace Seg1
{struct Node{int l,r,mmin,mmax;}tree[N<<2];void build(int k,int l,int r){tree[k].l=l;tree[k].r=r;if(l==r){scanf("%d",&tree[k].mmax);tree[k].mmin=tree[k].mmax;return;}int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);tree[k].mmax=max(tree[k<<1].mmax,tree[k<<1|1].mmax);tree[k].mmin=min(tree[k<<1].mmin,tree[k<<1|1].mmin);}int query_min(int k,int l,int r){if(tree[k].l>r||tree[k].r<l)return inf;if(tree[k].l>=l&&tree[k].r<=r)return tree[k].mmin;return min(query_min(k<<1,l,r),query_min(k<<1|1,l,r));}int query_max(int k,int l,int r){if(tree[k].l>r||tree[k].r<l)return -inf;if(tree[k].l>=l&&tree[k].r<=r)return tree[k].mmax;return max(query_max(k<<1,l,r),query_max(k<<1|1,l,r));}
}namespace Seg2
{struct Node{int l,r,mmin;}tree[N<<2];void build(int k,int l,int r){tree[k].l=l;tree[k].r=r;tree[k].mmin=inf;if(l==r)return;int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);}void update(int k,int pos,int val){if(tree[k].l==tree[k].r){tree[k].mmin=val;return;}int mid=tree[k].l+tree[k].r>>1;if(pos<=mid)update(k<<1,pos,val);elseupdate(k<<1|1,pos,val);tree[k].mmin=min(tree[k<<1].mmin,tree[k<<1|1].mmin);}int query(int k,int l,int r){if(l>r)return inf;if(tree[k].l>r||tree[k].r<l)return inf;if(tree[k].l>=l&&tree[k].r<=r)return tree[k].mmin;return min(query(k<<1,l,r),query(k<<1|1,l,r));}
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);int n,s,len;scanf("%d%d%d",&n,&s,&len);Seg1::build(1,1,n);Seg2::build(1,0,n);Seg2::update(1,0,0);for(int i=1;i<=n;i++){int l=1,r=i,mark=-1;while(l<=r){int mid=l+r>>1;int delta=Seg1::query_max(1,mid,i)-Seg1::query_min(1,mid,i);if(delta<=s){mark=mid;r=mid-1;}else{l=mid+1;}}if(mark!=-1)Seg2::update(1,i,Seg2::query(1,mark-1,i-len)+1);}if(Seg2::query(1,n,n)==inf)puts("-1");elseprintf("%d\n",Seg2::query(1,n,n));return 0;
}
?
總結(jié)
以上是生活随笔為你收集整理的CodeForces - 487B Strip(线段树+dp+二分)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
