[数据结构与算法]Codeforces B. MEX and Array

题目大意：给定一个序列，求出一个最大的sum，sum定义：对于一个片段，他的分割后的片段数+分割后每个片段的mex值之和设为X，sum就等于给出序列的所有子片段的X值和

思路：首先要求出最大的sum就要保证每个子段的X最大，而仔细观察不难发现，对于任意片段，其X的最大值等于其片段长度加片段中0的数量，这个结论为什么正确呢？举个例子，如片段{0,1,2}，他的X值是1+3=4，而无论如何分割，他的X值最大为4，如

{0}，{1}，{2}

{0,1}，{2}

{0}，{1,2}

这些值不可能大于4，原因是mex，mex的值决定了X大小，无论怎么分割。只有一个片段有0存在，mex值才可能增加，不然mex恒为0，这样少分割的话只会更亏。

简单分析一下，首先，假如该片段没有0，其长度越大越浪费，此时尽可能多的分割才是最优决策。其次，假如该片段有0，那么观察不难发现，从0开始每次递增1的序列(每个数字只出现一次)的X值就是该序列长度加1，此时如果序列中有重复数字，那X值一定不是最大，因为浪费了至少一次加分割数的机会，比如{0,1,2,3} {3}和{0,1,2,3,3}肯定是前者X大，而对于每个子段都遵循这个，所以对于这种情况还是尽可能多的分割是最优决策。

综上所述，对于任意子段情况，无限分割至每个子段有且仅有1个元素的X值必然最大，而0的mex等于1，所以别忘额外加上0的数量。至此，结论正确

Code：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 110;
int get(vector<int> q)
{
    int res=0;
    for(int i=0;i<q.size();i++)
    {
        if(q[i]) res++;
        else
        res+=2;
    }
    return res;
}
void solve()
{
    int n;
    cin>>n;
    
    int a[N]={0};
    for(int i=0;i<n;i++) cin>>a[i];
    
    int ans=0;
    for(int i=0;i<n;i++)
    {
        for(int j=i;j<n;j++)
        {
            vector<int> q;
            for(int k=i;k<=j;k++)
            q.push_back(a[k]);
            
            ans+=get(q);
        }
    }
    cout<<ans<<endl;
}
int main()
{
    int _;
    cin>>_;
    while(_--) solve();
    return 0;
}