灵山之上神风起

· · 题解

根据题目描述，首先可以证明的是，选取的 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=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;
}