P1545 Dividing the Path G（线段树+动态规划）
题目传送门
题意简化
使用长度为2A$\sim$2B的区间覆盖长度为L的线段，并给出n个子区间，要求每个子区间仅被同一区间覆盖，求最小的区间使用数量
思路
考虑\(dp_i\)表示覆盖0\(\sim\)L范围的最小使用数量，一条右端点在i处的线段左端点范围为i-2B\(\sim\)i-2A，我们可以在该范围内找出最小的dp值用于更新\(dp_i\)，使用线段树维护区间内最小的dp值
Code
//dp[i]=min(dp[j])+1,j->[i-2b,i-2a]
#include<iostream>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=1e6+5;
struct SegmentTree
{struct node{int l,r,data;}Tree[N<<2];int lazy[N<<2];void pushup(int k){Tree[k].data=min(Tree[k<<1].data,Tree[k<<1|1].data);}void pushdown(int k){if(!lazy[k]) return;lazy[k<<1]=lazy[k];Tree[k<<1].data=lazy[k];lazy[k<<1|1]=lazy[k];Tree[k<<1|1].data=lazy[k];lazy[k]=0;}void buildtree(int k,int L,int R){Tree[k].l=L,Tree[k].r=R;if(L==R){Tree[k].data=0x3f3f3f3f;return;}int Mid=(L+R)>>1;buildtree(k<<1,L,Mid);buildtree(k<<1|1,Mid+1,R);pushup(k);}void modify(int k,int L,int R,int val){if(L<=Tree[k].l&&Tree[k].r<=R){Tree[k].data=val;lazy[k]=val;return;}pushdown(k);if(L<=Tree[k<<1].r)modify(k<<1,L,R,val);if(R>=Tree[k<<1|1].l)modify(k<<1|1,L,R,val);pushup(k);}int query(int k,int L,int R){if(L<=Tree[k].l&&Tree[k].r<=R)return Tree[k].data;pushdown(k);int res=0x3f3f3f3f;if(L<=Tree[k<<1].r)res=min(res,query(k<<1,L,R));if(R>=Tree[k<<1|1].l)res=min(res,query(k<<1|1,L,R));return res;}
}Segment;
bool vis[N];
int n,len,A,B,dp[N];
int main()
{IOS;cin>>n>>len>>A>>B;Segment.buildtree(1,0,len);Segment.modify(1,0,0,0);//dp[0]赋初始值为0for(int i=1;i<=n;i++){int st,ed;cin>>st>>ed;for(int j=st+1;j<=ed-1;j++)vis[j]=true;}for(int i=2*A;i<=len;i+=2){if(vis[i]) continue;int L=max(0,i-2*B),R=i-2*A,tmp=Segment.query(1,L,R);//注意边界问题dp[i]=tmp+1,Segment.modify(1,i,i,dp[i]);//每次求得dp[i]后更新线段树中的值}cout<<(dp[len]>=0x3f3f3f3f?-1:dp[len])<<'\n';return 0;
}
完结撒花～