Codeforces B. MEX and Array

The main idea of the topic ： Given a sequence , Find a maximum sum,sum Definition ： For a segment , The number of segments after his segmentation + Of each segment after segmentation mex The sum of the values is set to X,sum It is equal to giving all the sub segments of the sequence X Values and

Ideas ： First, ask for the largest sum It is necessary to ensure that each sub segment X Maximum , But careful observation is not difficult to find , For any fragment , Its X The maximum value of is equal to the length of the fragment plus the length of the fragment 0 The number of , Why is this conclusion correct ？ for instance , Such as fragments {0,1,2}, His X The value is 1+3=4, And no matter how it is divided , His X The maximum value is 4, Such as

{0},{1},{2}

{0,1},{2}

{0},{1,2}

These values cannot be greater than 4, as a result of mex,mex The value of determines X size , No matter how divided . Only one segment has 0 There is ,mex Value can be increased , Otherwise mex Constant for the 0, Such a small Division will only lead to more losses .

A brief analysis of , First , If the clip does not 0, The longer it is, the more wasteful it is , At this point, the optimal decision is to divide as many as possible . secondly , If the clip has 0, Then it is not difficult to observe , from 0 Start each increment 1 Sequence ( Each number appears only once ) Of X Value is the length of the sequence plus 1, In this case, if there are repeated numbers in the sequence , that X The value must not be the maximum , Because at least one chance to add the number of partitions is wasted , such as {0,1,2,3} {3} and {0,1,2,3,3} It must be the former X Big , This is followed for each sub segment , So for this case, it is the best decision to divide as many as possible .

in summary , For any sub segment , Infinitely split to each sub segment with and only 1 An element of X The value must be the maximum , and 0 Of mex be equal to 1, So don't forget to add 0 The number of . thus , The conclusion is correct

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;
}