自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 22:39:58，当前版本为作者最后更新于2022-09-10 20:54:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

根据题目描述，首先可以证明的是，选取的 $a_i \neq 1$ 的点的个数不会大于等于 $3$。

这是因为，当选取了 $a_i \neq 1$ 的节点数量恰为 $2$ 的时候，只有一种在左侧位置 $l$ 选择一个 $a_i=2$ 的节点，在右侧位置 $r$ 选择一个 $a_i=3$ 的节点的情况下不会产生冲突（即，存在方案使得选出的点集是个独立集）。此时若是再选择一个 $a_i \neq 1$ 的节点，例如说在 $l<x<r$ 的位置 $x$ 选择一个 $a_i=2$，则无法和 $l$ 位置上的节点构成独立集；选择 $a_i=3$，则无法和 $r$ 位置上的节点构成独立集。其余四种情况（$1 \leq x<l$ 与 $r<x \leq n$）同理。

因此得出，选择的节点中，$a_i \neq 1$ 的节点个数为 $0,1,2$。若一个 $a_i \neq 1$ 的都不选，就是都选择 $a_i=1$ 的节点，这个时候构成的独立集在这个情况下是最大的。

若选择一个 $a_i \neq 1$ 的节点，就会分成两个情况。若选择一个 $a_i=2$ 的节点，即向所有编号 $<i$ 的节点连边，我们希望在这个情况下被连边连接到的 $a_i=1$ 的节点最少。因此我们让这个 $a_i=2$ 的节点选择的尽可能靠左，这样其右边的 $a_i=1$ 的节点都是可选放入独立集的；对于选择一个 $a_i=3$ 的情况是同理的。

若选择两个 $a_i \neq 1$ 的节点，如上文所述，只有一种在左侧位置 $l$ 选择一个 $a_i=2$ 的节点，在右侧位置 $r$ 选择一个 $a_i=3$ 的节点的情况下不会产生冲突，这个时候在 $l<x<r$ 范围内的 $a_x=1$ 都是可选择放入独立集的。

综上所述，我们所选取的节点有如下可能：

• 选取所有 $a_i=1$ 的点；
• 选取最左边的 $a_i=2$ 的点，再选取所有其右边的 $a_i=1$ 的点；
• 选取最右边的 $a_i=3$ 的点，再选取所有其左边的 $a_i=1$ 的点；
• 选取最左边的 $a_i=2$ 的点和最右边的 $a_i=3$ 的点，再选取所有其中间的 $a_i=1$ 的点。

四种情况分别讨论一下看哪一个选取的点更多。注意第四种情况下需要判断最左边的 $a_i=2$ 的点和最右边的 $a_i=3$ 的点的位置，否则容易被如下数据卡住（正确答案是 $1$）：

2
3 2

参考代码：

#include <iostream>

using namespace std;

int n,a[100050],l,r;

int main()
{
	cin >> n;
	for (int i=1;i<=n;i++)
		cin >> a[i];
	for (int i=1;i<=n;i++)
	{
		if (a[i]==2)
		{
			l=i;
			break;
		}
	}
	for (int i=n;i>=1;i--)
	{
		if (a[i]==3)
		{
			r=i;
			break;
		}
	}
	int ans=0;
	if (l)
	{
		int ret=1;
		for (int i=l+1;i<=n;i++)
			ret+=(a[i]==1);
		ans=max(ans,ret);
	}
	if (r)
	{
		int ret=1;
		for (int i=1;i<=r-1;i++)
			ret+=(a[i]==1);
		ans=max(ans,ret);
	}
	if (l && r && r>l)//第四种情况的特判
	{
		int ret=2;
		for (int i=l+1;i<=r-1;i++)
			ret+=(a[i]==1);
		ans=max(ans,ret);
	}
	int ret=0;
	for (int i=1;i<=n;i++)
		ret+=(a[i]==1);
	ans=max(ans,ret);
	cout << ans << endl;
	return 0;
}