洛谷 P4644 USACO05DEC Cleaning Shift/AT_dp_w Intervals 题解

1.Cleaning Shift

题意

约翰的奶牛们从小娇生惯养，她们无法容忍牛棚里的任何脏东西。约翰发现，如果要使这群有洁癖的奶牛满意，他不得不雇佣她们中的一些来清扫牛棚，约翰的奶牛中有 $n$ 头愿意通过清扫牛棚来挣一些零花钱。

由于在某个时段中奶牛们会在牛棚里随时随地地乱扔垃圾，自然地，她们要求在这段时间里，无论什么时候至少要有一头奶牛正在打扫。需要打扫的时段从某一天的第 $st$ 秒开始，到第 $en$ 秒结束 。注意这里的秒是指时间段而不是时间点，也就是说，每天需要打扫的总时间是 $en-st+1$ 秒。

约翰已经从每头牛那里得到了她们愿意接受的工作计划：对于某一头牛，她每天都愿意在笫 $l\dots r$ 秒的时间段内工作 $(st\le l\le r\le en)$ ，所要求的报酬是 $k$ 美元 $(0\le k\le 500000)$。与需打扫时段的描述一样，如果一头奶牛愿意工作的时段是每天的第 $10\dots 20$ 秒，那她总共工作的时间是 $11$ 秒，而不是 $10$ 秒。

约翰一旦决定雇佣某一头奶牛，就必须付给她全额的工资，而不能只让她工作一段时间，然后再按这段时间在她愿意工作的总时间中所占的百分比来决定她的工资。现在请你帮约翰决定该雇佣哪些奶牛以保持牛棚的清洁，当然，在能让奶牛们满意的前提下，约翰希望使总花费尽量小。

$1\le n\le 10000,0\le st\le en\le 86399$

思路

最小权线段覆盖，CSPS2024就倒在这种类型。

套路地，我们对每一只奶牛的工作区间按右端点排序。

定义$f_r$表示从$st$清理到$r$的最小花费，那么朴素的，对于一只工作时间段右端点恰为$r$的奶牛$t$，我们可以写出转移式子：
$$f_r=\underset{r_t=r}{\min }\left\{k_t+\underset{i=1}{\overset{l_t-1}{\min }}{f}_i\right\}$$

看到区间最小值如果暴力做就$\Theta (n^2)$，然而显然的我们可以用线段树求区间最小值来凹时间。

最后就是一些细节：考虑其花费最大值都去到了$500000$，那么$\mathrm{INF}$值要给大一点，开long long吧别吝啬那点空间；然后就是给最好给时间点都加$1$防$0$，不然减$1$的时候出现$-1$就段错误了。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls u<<1
#define rs u<<1|1 
const ll N=1e5+9,inf=3e14;
ll n,st,en;
struct term
{
	ll l,r,k;
};
vector<term>p[N];
ll f[N];
struct SegT
{
	struct node
	{
		ll mi;
	}T[N<<2];
	void pushup(ll u)
	{
		T[u].mi=min(T[ls].mi,T[rs].mi);
	}
	void build(ll u,ll l,ll r)
	{
		T[u].mi=inf;
		if(l==r)return;
		ll mid=(l+r)>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
		pushup(u);
	}
	void modify(ll u,ll l,ll r,ll x,ll k)
	{
		if(l==r)
		{
			T[u].mi=min(T[u].mi,k);
			return;
		}
		ll mid=(l+r)>>1;
		if(x<=mid)modify(ls,l,mid,x,k);
		if(x>mid)modify(rs,mid+1,r,x,k);
		pushup(u);
	}
	ll query(ll u,ll l,ll r,ll ql,ll qr)
	{
		if(qr<l||r<ql)return inf;
		if(ql<=l&&r<=qr)return T[u].mi;
		ll mid=(l+r)>>1,ret=inf;
		if(ql<=mid)ret=min(ret,query(ls,l,mid,ql,qr));
		if(qr>mid)ret=min(ret,query(rs,mid+1,r,ql,qr));
		return ret;
	}
}A;
int main()
{
	scanf("%lld%lld%lld",&n,&st,&en);
	st++,en++;
	for(int i=1;i<=n;i++)
	{
		ll l,r,k;
		scanf("%lld%lld%lld",&l,&r,&k);
		l++,r++;
		l=max(l,st);
		r=min(r,en);
		p[r].push_back((term){l,r,k});//对右端点排序
	}
	for(int i=st;i<=en;i++)
	f[i]=inf;
	A.build(1,st-1,en);
	A.modify(1,st-1,en,st-1,0);//不用干就0咯
	f[st-1]=0;
	for(int i=st;i<=en;i++)//枚举右端点r
	{
		for(auto x:p[i])//遍历奶牛
		{
			f[i]=min(f[i],x.k+A.query(1,st-1,en,x.l-1,i));
			A.modify(1,st-1,en,i,f[i]);//贡献扔进右端点对应线段树
		}
	}
	if(f[en]==inf)puts("-1");
	else printf("%lld",f[en]);
	return 0;
}

2.Intervals

题意

给定$m$条规则，形如$l,r,k$，对于一个$01$串，其分数的定义为：对于第$i$条规则，若该串在区间$[l,r]$中至少有一个$1$，则该串的分数增加$k$。

求长度为$n$的$01$串最大分数。

$1\le n,m\le 2\times 10^5,-10^9\le k\le 10^9$

思路

令$f_{r,j}$表示枚举到位置$r$，上一个$1$放在$j$处的最大答案。
f r , j = max ⁡ j = 1 r − 1 { f r − 1 , j } + ∑ i : l i ≤ r k i f_{r,j}=\max_{j=1}^{r-1}\{f_{r-1,j}\}+\sum_{i:l_i\le r}k_i fr,j​=j=1maxr−1​{fr−1,j​}+i:li​≤r∑​ki​

那就还是线段树优化dp了。

同样，根据右端点排序，线段树维护贡献最大值即可，对于所有满足$l_i\le r,r_i=r$的奶牛$i$的分数和，也扔上线段树区间加并入贡献即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls u<<1
#define rs u<<1|1
const ll N=2e5+9,inf=0x7f7f7f7f;
ll n,m;
struct term
{
	ll l,r,k;
};
vector<term>p[N];
struct SegT
{
	struct node
	{
		ll ma;
		ll tag;
	}T[N<<2];
	void pushup(ll u)
	{
		T[u].ma=max(T[ls].ma,T[rs].ma);
	}
	void pushdown(ll u)
	{
		if(T[u].tag)
		{
			T[ls].tag+=T[u].tag;
			T[ls].ma+=T[u].tag;
			T[rs].tag+=T[u].tag;
			T[rs].ma+=T[u].tag;
			T[u].tag=0;
		}
	}
	void modify(ll u,ll l,ll r,ll ql,ll qr,ll k)
	{
		if(ql<=l&&r<=qr)
		{
			T[u].ma+=k;
			T[u].tag+=k;
			return;
		}
		pushdown(u);
		ll mid=(l+r)>>1;
		if(ql<=mid)modify(ls,l,mid,ql,qr,k);
		if(qr>mid)modify(rs,mid+1,r,ql,qr,k);
		pushup(u);
	}
}A;
int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++)
	{
		ll l,r,k;
		scanf("%lld%lld%lld",&l,&r,&k);
		p[r].push_back({l,r,k});//右端点排序 
	}
	for(int i=1;i<=n;i++)
	{
		A.modify(1,1,n,i,i,max(0ll,A.T[1].ma));
		for(term x:p[i])
		A.modify(1,1,n,x.l,i,x.k);//右端点加贡献 
	}
	printf("%lld",max(0ll,A.T[1].ma));
	return 0;
}