题解：AT_arc137_b [ARC137B] Count 1's

· · 题解

看到题解区居然没有相同的做法有些惊讶，感觉我的思路更自然一些。

所有得分的情况等于最大得分减去最小得分再加一^1，其他题解说的很详细了这里不再赘述。

问题转化为求最大得分和最小得分。我们只讨论求最大得分，不失其一般性^2。

先统计全部的 1 的个数。不难发现操作序列中每一个 0 造成 +1 的贡献，每一个 1 造成 -1 的贡献。我们考虑扫描每一段极大的^3对得分造成非负贡献的操作序列，这样可以用双指针优化，因为我们能够把整个序列拆成若干个不相交的极大的序列，中间被一个 1 隔开。假设已经选了一段操作序列，如果这一段序列贡献小于零，那么把他丢掉再从当前位置开始扫描一定是更优的。由于我们不知道答案在何处取得，所以在内层扫描时去一个最大值即可。

核心代码

//为了代码简洁略去无关片段，只放了求最大值的部分。
int n,a[MAX];
void solve()
{
    cin>>n;
    fo(i,1,n)
        cin>>a[i];
    int sum=0,maxs=0;
    fo(i,1,n)
        sum+=a[i];
    maxs=sum;
    int i=1,j=1;
    for(i=1;i<=n;)
    {
        int d=0;
        for(j=i;j<=n;j++)
        {
            if(a[j]==0)
                d++;
            else
                d--;
            maxs=max(maxs,sum+d);
            if(d<0)
                break;
        }
        i=j+1;
    }
}

AC 记录