题解 P6631 【[ZJOI2020] 序列】
ReseeCher
·
·
题解
约定覆盖位置[l],[l+1],[l+2]......[r]的为一条从l开始的“直线”
约定覆盖位置[l],[l+2],[l+4]......[r]的为一条从l开始的“跳线”
那么原问题相当于使用一些直线和跳线使每个位置i刚好被a[i]条线覆盖
每用一条线称作1个cost,我们希望总的cost最小
首先考虑如何去覆盖第1和第2个位置
为了方便，这里a[i]表示位置i还要被几条线段覆盖
这里先给出方案：
-
-
-
prove1
比较显然，位置2已经不能被覆盖，只能连出跳线
prove2
考虑证明以下命题：从1开始的连续非0区间（长度>=2）用一条直线覆盖一定不劣
设这段区间为[1,r]，那么因为a[r+1]=0，所以不可能向后连出直线，唯一有利于后面位置被覆盖的方案是在与(r)奇偶性相同的位置连出一条跳线
但是这样做必有cost>=2，而使用一条直线和一条跳线cost为2，所以一定不优于原方案（不如从后面开始跳线）
此时由于a[1]=0了，我们可以把位置1删除，继续考虑第2和第3个位置
这个问题与刚才的问题类似，唯一的区别是要处理被前面开始的线覆盖的情况
如果能被前面的线覆盖则一定被覆盖，因为这样cost=0，而任意一种可能更利于后面被覆盖的方案都需要cost=1，不如从后面开始
若前面的直线有A个，能连到3的跳线有B个
那么如果a[3]>=A+B，直接把a[3]减去A+B即可
但如果a[3]<A+B，则一定有A+B-a[3]条线无法连下去，记为K
发现保留直线还是跳线和后面的位置有关，于是我们可以先把A和B都减去K，再在3上打K个标记，表示可以从3免费开始K条任意的线
但这时候出现了一个新的问题，A和B不能被减到负数
注意到若K>A，那么B至少也要断掉K-A条，那么先把这些边断掉，这样就没有问题了
---
这样我们就有一个可以从$(a[i-1],a[i])$推到$(a[i],a[i+1])$的算法了，一遍推过去即可
具体可以看代码中的注释
```cpp
void Work(){
LL A=0,B=0,C=0,Ans=0,D=0; //C表示奇偶性为另一类的跳线个数
F(i,2,n+1){
if(a[i]<B+A){ //处理被前面的线覆盖的情况
int K=B+A-a[i];
if(B<K)A-=K-B,K-=K-B;
if(A<K)B-=K-A,K-=K-A;
B-=K;A-=K;a[i]-=K;D=K; //D：记录标记个数
}
a[i]-=A+B;
LL U=min(a[i-1],a[i]); //U：新增直线个数
Ans+=U;a[i-1]-=U;a[i]-=U;A+=U; //处理直线
Ans+=a[i-1];C+=a[i-1];a[i-1]=0; //处理跳线
a[i]+=D;Ans-=D;D=0; //处理标记
swap(B,C); //奇偶性互换
}
cout<<Ans<<'\n';
}
```