Codeforces Round ＃809 (Div. 2), problem: (C) Qpwoeirut And The City

One . The question  

Here you are. n A row of buildings , Each building has a height index h[i], We define when i>=2 && i<=n-1 When... When , if h[i]>=h[i-1]&&h[i]>=h[i+1]  So this building is cool ！

Now that you have bricks and tiles, you can add floors to any building , But the existing floors cannot be dismantled .

Your goal is to use the least bricks , Maximize the number of cool buildings .

Two . Ideas

At the bottom is a summary , If you think the following explanation is too long, you can directly see the following summary , If there is something you don't understand, you can see my detailed explanation .

Let's discuss it according to the situation

① If n If it's an odd number , that 2~n-1 A building of must be a height ………… High interleaved sort , Because if there are n A building , Eventually there will be (n-1+2)/2（ Rounding up formula (n+m-1）/m） A cool building , So it must end up like this , You can draw a picture and have a look （ One of my own problems is that I always dream , Then maybe what you think is wrong , But I didn't write and draw with my pen , I think it's right , Committed “ I thought ” Error of ） In this case, we only need to enumerate and change to see how many bricks and tiles are needed to turn into this arrangement .

② If n If it's even , If there is n A building , Eventually there will be n/2（ Rounding up formula ） A cool building .

【 For the sake of brevity here The cool architecture is abbreviated as high Not cool architecture is abbreviated as low 】

And these cool buildings must appear at intervals , After preliminary thinking , I think it can be high or low …… High or low, high or low …… Low and high schemes , But let's take a look at the sample ：

6
1 10 1 1 10 1

It is found that 1 Time Two high and two low in the middle This is also satisfying n/2 A cool building .

But this situation begins with 2 A building must be tall , That is, cool architecture , And we can find that ruodi i The building is tall , The first i+1 and i+2 If all buildings are low , In fact, the arrangement rhythm of buildings is from high to low …… High and low （ The first 2 Buildings are arranged alternately after being high ）  stay i+2 Place is replaced by low high high …… Low high （ The first 2 The buildings are arranged alternately after being low ）, So we use the idea of prefix and to write it down separately   front i individual Building utilization    Low high high …… Low high Rhythm and   High and low …… High and low The number of all bricks in a rhythm , And then in each i Hypothesis appears The first i The building is tall , The first i+1 and i+2 All buildings are low （ Rhythm changes ） In this case , Make a calculation of the number of bricks , The formula is ans1[i]+ans2[n-1]-ans2[i+1], among ans1[i] It's the front i A building becomes high and low …… The number of bricks used in a high-low arrangement ,ans2[i] It's the front i Buildings become low and high …… The number of bricks used for a low and high arrangement , that ans2[n-1]-ans2[i+1] Is to put i+1 The building after the building becomes low and high …… The number of bricks used for a low and high arrangement , therefore ans1[i] and ans2[n-1]-ans2[i+1] Add up to the whole i Hypothesis appears The first i The building is tall , The first i+1 and i+2 All buildings are low （ Rhythm changes ) A brick number .

So in this case, just enumerate a turning point ！

To sum up ：

Two situations ： 

1.n It's odd   To maximize the cool architecture, an arrangement form is fixed , Direct enumeration ans.

2.n For the even , Three situations ：

① The first 2 Buildings are low , Then the arrangement form is also fixed , You can get ans, That is, prefix and ans2[n-1].

② The first 2 A building is tall , The first n-1 Buildings are low , Then the arrangement form is also fixed , You can get ans, That is, prefix and ans1[n-2].

③ The first 2 A building is tall , The first n-1 A building is tall , Then there must be a turning point i bring The first i The building is tall , The first i+1 and i+2 All buildings are low , At this time, there will be a high-low …… High and low （ The first 2 Buildings are arranged alternately after being high ）  stay i+2 Place is replaced by low high high …… Low high （ The first 2 The buildings are arranged alternately after being low ） A transformation , So we use prefixes and arrays , Write down and use these two rhythms to achieve the first i The number of bricks used in a building , Then enumerate this turning point .

See here is almost over , I'm glad you can click in , If the article helps you , Can you click on the small hand below ？ Your support is the greatest encouragement to my creation ！

3、 ... and . Code

#include <iostream>
#include <cstring>
#include <algorithm>
#include<map>
using namespace std;
map<int,int> st,cnt; 
const int N = 2e5+10;
typedef long long LL;
int n;
int a[N];
LL ans1[N],ans2[N];

void solve()
{
    
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int i=1;i<=n+2;i++)
    {
        ans1[i]=0;
        ans2[i]=0;
    }
    LL ans=0;
    if(n&1) //n It's odd 
    {
        for(int i=2;i<=n-1;i+=2)
        {
            if(a[i]<=a[i-1]||a[i]<=a[i+1])
            {
                ans+=max(a[i-1],a[i+1])-a[i]+1;
            }
        }
        
    }
    else//n For the even 
    {
        ans=2e14;// Do not forget to initialize ans Is the data maximum ！
        for(int i=2;i<=n-1;i+=2)// there i On behalf of the first i One becomes high , So interval fetching 
        {
            if(a[i]<=a[i-1]||a[i]<=a[i+1])
            {
                ans1[i]+=max(a[i-1],a[i+1])-a[i]+1;// High and low rhythm down front i Number of bricks used 
            }
            if(i>=4) ans1[i]+=ans1[i-2];
        }
        for(int i=3;i<=n-1;i+=2)// there i On behalf of the first i One becomes high , So interval fetching 
        {
            if(a[i]<=a[i-1]||a[i]<=a[i+1])
            {
                ans2[i]+=max(a[i-1],a[i+1])-a[i]+1;// Low high and low, high rhythm, front i Number of bricks used 
            }
            if(i>=3) ans2[i]+=ans2[i-2];
        }
        for(int i=2;i<=n-4;i+=2)
        {
            ans=min(ans,ans1[i]+ans2[n-1]-ans2[i+1]); situation ③ The minimum value of 
        }
        ans=min(ans,min(ans1[n-2],ans2[n-1]));// situation ①②③ Minimum value 
    }
    cout<<ans<<endl;
    
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }
}