线段树优化DP

AC记录：

运行时间完爆zmrzmr的单调队列优化+双指针 p[i]表示右端点小于i的左端点的最大值,f[i]表示将左端点在i这个位置前的所有线段覆盖的最小花费 $$f[i]=min {f[j]}~(p[i]<=j<i)~$$ 用线段树查询最小值 时间复杂度 $$ O(nlogn) $$

注意

要将n加一，花费计算到n+1，否则下面这样的数据将无法通过（我在这个地方卡了一小时）

5
1 1 1 1 1
2
1 5
4 5

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int N=5e5+10;
int n,a[N],m,f[N],mx[N];
struct tree {
	int l,r,minn;
} tr[N*4];
struct node {
	int l,r;
	bool operator<(const node &x) {
		return r<x.r;
	}
} line[N];
void build(int u,int l,int r) {
	tr[u]= {l,r};
	if(l==r) return;
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
}
void pushup(int u) {
	tr[u].minn=min(tr[u<<1].minn,tr[u<<1|1].minn);

}
int query(int u,int l,int r) {
	if(l<=tr[u].l&&tr[u].r<=r) return tr[u].minn;
	int ans=0;
	int mid=tr[u].l+tr[u].r>>1;
	if(l<=mid) ans=query(u<<1,l,r);
	if(r>mid) ans=(ans==0?query(u<<1|1,l,r):min(ans,query(u<<1|1,l,r)));
	return ans;
}
void modify(int u,int x,int v) {
	if(tr[u].l==x&&tr[u].r==x)     tr[u].minn=v;
	else {
		int mid=tr[u].l+tr[u].r>>1;
		if(x<=mid) modify(u<<1,x,v);
		else modify(u<<1|1,x,v);
		pushup(u);
	}
}
int query2(int pos) {
	int i=lower_bound(line+1,line+1+m,node{0,pos})-line-1;
	return mx[i];
}
signed main() {
	cin>>n;
	for(int i=1; i<=n; i++) cin>>a[i];
	cin>>m;
	for(int i=1; i<=m; i++) cin>>line[i].l>>line[i].r;
	sort(line+1,line+1+m);
	mx[0]=0;
	for(int i=1; i<=m; i++) mx[i]=max(line[i].l,mx[i-1]);
	build(1,1,n+1);
	for(int i=1; i<=n+1; i++) {
		int lastpos=query2(i);
		if(lastpos==0) f[i]=a[i];
		else f[i]=query(1,lastpos,i-1)+a[i];
		modify(1,i,f[i]);
	}
	int ans=2e9;
	//for(int i=max(1LL,query2(n));i<=n;i++) ans=min(ans,f[i]);
	cout<<f[n+1];
}

因为每个点的代价不同，所以不能直接贪心做区间选点问题，但是可以利用类似的思路。

设 $f_i$ 表示前 $i$ 个点中，第 $i$ 个点必选的最小代价。

考虑转移，设转移决策点为 $j$，那么必然要满足的条件是对于所有右端点小于 $i$ 的区间，$j$ 不能小于这些区间的左端点，否则这个区间就会被漏选（因为后面的决策点也选择不了这些漏选的区间）。

设 $x_i$ 表示右端点小于 $i$ 的区间左端点最大值。

然后就可以写出状态转移方程：

$f_i = a_i + \min_{j = x_i}^{i-1} f_j$

具体实现就将所有区间按右端点从小到大排序，双指针维护最大值。因为这个决策点是单调递增的，所以可以使用单调队列优化。

最终的答案也即：

$min_{j = x_n}^{n} f_j$ ​

时间复杂度 $O(mlogm)$，瓶颈在于区间排序，动态规划部分的时间复杂度为 $O(n+m)$。

#include<bits/stdc++.h>
#define MAXN 500005
using namespace std;
typedef long long LL;
int n,m,a[MAXN];
struct SEG{
	int l,r;
	bool operator < (const SEG&B)const{return r<B.r;}
}e[MAXN];
LL f[MAXN];
int q[MAXN],h,t;
void solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	scanf("%d",&m);
	for(int i=1;i<=m;i++) scanf("%d%d",&e[i].l,&e[i].r);
	sort(e+1,e+m+1);
	int l=0;
	h=1,t=0,q[++t]=0;
	for(int i=1,j=1;i<=n;i++){
		f[i]=f[q[h]]+a[i];
		while(h<=t&&f[q[t]]>f[i]) --t;
		q[++t]=i;
		for(;j<=m&&e[j].r<=i;j++) l=max(l,e[j].l);//双指针维护最大值。
		while(h<=t&&q[h]<l) ++h;
	}
	printf("%lld\n",f[q[h]]);
}
int main(){
    int T = 1;
    while(T--) solve();
    return 0;
}