自动搬运

查看原文

来自洛谷，原作者为

	sail_with_pleasure 这个家伙很懒，因为真的很懒

搬运于2025-08-24 22:48:54，当前版本为作者最后更新于2023-06-23 09:43:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

为了与题面统一，称 $a_i$ 状态 $\tt 1 \to \tt 0$ 为消除，$\tt 0 \to \tt 1$ 为点亮。

算法零

由于状态只有 $2^n$ 种，因此记忆化所有状态，爆搜转移。

时间复杂度 $\mathcal O(n^32^n + T)$，可以通过 Subtask 0。

算法一

按算法四的思想模拟即可，不过多赘述。

时间复杂度 $\mathcal O(\sum n^2)$。

算法二

考虑初始灯全为 $0$。

这个时候，勇士可以直接贪心地先点亮所有编号为奇数的格子，这样魔王每次只能消除一个 $\tt 1$；直到勇士只能往 $\tt 1$ 空隙中点亮为止。

可以选择任何计算方法，时间复杂度 $\mathcal O(\sum n)$，还可以通过推结论的方法做到更优。

算法三

考虑数据随机。

一些缺少一些细节的贪心以及乱搞做法应该都能通过。

算法四

考虑魔王的每次消除 $\tt 1$ 的行动，按照时间推移，它形如：

• A 段：若干次连续消除两个 $\tt 1$（可能没有）；
• B 段：若干次消除一个 $\tt 1$（可能没有）；
• C 段：若干次连续消除两个 $\tt 1$（如果一开始就是全 $\tt 1$ 那也可能没有）。

由于 A 段和 C 段每一天都只比前一天增加一盏亮着的灯，所以只需求出在 B 段花费的时间即可计算总时间。

考虑 A 段：先贪心地模拟魔王，每次消掉两个连续的 $\tt 1$，并直接算出它的时间。

在 A 段魔王消除之时，我们可以假设勇士知道魔王会如此消除（事实上，根据魔王每一步的消除，针对性地再点亮一些灯也可行），那么他的最优策略肯定是：在保证任意两个 $\tt 1$ 不连续的前提下，点亮尽可能多的 $\tt 1$，可以用 dp 求解。

考虑 B 段：由于魔王每次都会采取最优策略，那么勇士补上每次魔王消掉的那一盏灯，这同样也是最优的。可能有形如 $\tt{010000001000}$ 的特殊情况，即魔王第一天无论怎么选择都比较劣，可以首先进行一轮模拟或者特判掉。剩下的时间，就相当于每天点亮两盏灯。

考虑 C 段：在 A / B 段都已经求出来的情况下，可以直接求解。

时间复杂度 $\mathcal O(\sum n)$。

代码如下：

#include<bits/stdc++.h>
#define pi pair<int,int> 
#define mid (l+r)/2
#define N 1000001
using namespace std;
int t,n,a[N],cnt,cnt1,dp[N],ans,cnt2,flag,flag1,pre[N],nxt[N];
int pan(){//单消段特判 
	int x=-1;
	for(int i=1;i<=n;i++){//计算每两个 1 之间的间隔 
		if(a[i]){
			pre[i]=i-x-1;
			nxt[i]=n+1-i;
			if(x>0)nxt[x]=pre[i];
			x=i;
		}
	}
	for(int i=1;i<=n;i++){//判断是否有较优的单消情况 
		if(a[i]==1&&((pre[i]%2==1||nxt[i]%2==1)||a[i-1]==1||a[i+1]==1)){
			return 0;
		}
	}
	if(a[n]==1)return 0;
	return 1;
}
int main(){
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=0;i<=n+2;i++){
			a[i]=pre[i]=nxt[i]=dp[i]=0;
		}
		cnt=cnt1=ans=cnt2=flag=flag1=0;
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			if(a[i])ans++,flag=1;
		}
		if(pan())flag1=1;
		for(int i=1;i<=n;i++){//判断初始双消段的长度 
			if(a[i]==a[i+1]&&a[i]==1){
				a[i]=a[i+1]=0;
				cnt++;
			}
		}
		for(int i=1;i<=n;i++){
			if(a[i]==1){
				dp[i]=max(dp[i-2],dp[i-3]);
			}else if(a[i+1]!=1&&a[i-1]!=1){
				dp[i]=max(dp[i-2],dp[i-3]);
				dp[i]++;
			}
			cnt1=max(cnt1,dp[i]);
		}
		if(n<=3){
			if(ans<n)cout<<1<<endl;
			else cout<<0<<endl;
			continue;
		}
		if(cnt1/3<cnt){//判断是否存在单消段 
			cout<<n-ans<<endl; 
			continue;
		}
		cnt1=cnt1-cnt*3;
		if(flag1&&flag)cnt1++;
		if(flag)cout<<n-ans-cnt1/2-1<<endl;
		else if(n<=5)cout<<2<<endl;
		else cout<<n-(cnt1-3)/2-3<<endl;	
	}	
	return 0;
}

PS：这题据说可能有神秘的 bitset 或者线段树等做法，大家可以试一试。