题解：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 的情况。分几种情况讨论：

分析完性质，就可以开始 dp 了。设 f_{i,j} 表示前 i 个表演者的喷酒范围为 [1,j] 的最小代价。

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

这个转移可以用单点修改区间求最小值的线段树维护，复杂度 O(n\log n)。下面给出代码：

#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;
}