题解：P11656 「FAOI-R5」喷酒大赛

首先，最优方案中给了钱的表演者是不会因为被喷酒而退场的，否则删除这个表演者对喷酒的范围不会产生影响。

其次，

k

是骗人的，代码中不读进来都行。考虑选择的两个表演者的喷酒范围分别为

[l_1,r_1]

和

[l_2,r_2]

（假设

l_1\le l_2

），若

r_2\le r_1

，那么第二个表演者显然没有存在的必要，于是我们只考虑

r_1\le r_2

的情况。分几种情况讨论：

$b_1=1,b_2=-1$ ：两个表演者互不影响
$b_1=-1,b_2=1$ ：由上面的分析知，不会出现这种情况
$b_1=b_2=1$ ：此时就算 $k_1=0$ ，第二个表演者仍旧会接着 $r_1$ 继续喷酒，所以无论 $k$ 的值是多少，喷酒的范围都是 $[l_1,r_2]$
$b_1=b_2=-1$ ：与上面类似，这里就不多赘述了

分析完性质，就可以开始 dp 了。设

f_{i,j}

表示前

i

个表演者的喷酒范围为

[1,j]

的最小代价。

$f_{i,j}=f_{i-1,j}$ ：不选择第 $i$ 个表演者
$f_{i,\min(n,i+a_i-1)}=\min_{j=i-1}^nf_{i-1,j}$ ，向右喷酒
$f_{i,i}=\min_{j=\max(0,i-a_i)}^{i-1}f_{i-1,j}$ ，向左喷酒

实现的时候要注意一个细节，一定要先转移向右喷酒再转移向左喷酒，否则就可以让当前的表演者既向左又向右，这种情况显然不合法。

这个转移可以用单点修改区间求最小值的线段树维护，复杂度

O(n\log n)

。下面给出代码：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
struct tree{
	int l,r,pre;
}t[N<<2];
void build(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	if(l==r){
		if(l)t[p].pre=1e9;
		return;
	}
	int mid=l+r>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	t[p].pre=min(t[p*2].pre,t[p*2+1].pre);
}
void change(int p,int x,int y){
	if(t[p].l==t[p].r){
		t[p].pre=min(t[p].pre,y);
		return;
	}
	int mid=t[p].l+t[p].r>>1;
	if(x<=mid)change(p*2,x,y);
	else change(p*2+1,x,y);
	t[p].pre=min(t[p*2].pre,t[p*2+1].pre);
}
int ask(int p,int x,int y){
	if(x<=t[p].l&&t[p].r<=y){
		return t[p].pre;
	}
	int mid=t[p].l+t[p].r>>1,ans=1e9;
	if(x<=mid)ans=min(ans,ask(p*2,x,y));
	if(y>mid)ans=min(ans,ask(p*2+1,x,y));
	return ans;
}
int n,a;
int main(){
	cin>>n;
	build(1,0,n);
	for(int i=1;i<=n;i++){
		cin>>a;
		change(1,min(n,i+a-1),ask(1,i-1,n)+1);
		change(1,i,ask(1,max(0,i-a),i-1)+1);
	}
	cout<<ask(1,n,n);
	return 0;
}

题解：P11656 「FAOI-R5」喷酒大赛

文章操作

相关推荐

评论

题解：P11656 「FAOI-R5」喷酒大赛