CF-Qpwoeirut And The City

如果n为奇数，那只有一种情况，就是从2开始间隔一个，到n - 1结束。如果n为偶数，则可能从2开始，也可能从3开始（无论从哪开始都到n - 1结束）,还可能是两种情况的混合（在某一段从高低高低到高低底高）

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 2e5 + 10;
typedef long long LL;
typedef pair<int, int> PII;
int a[N];

LL ans1[N], ans2[N];
int main()
{
  int t;
  cin >> t;
   while(t --)
   {
      int n;
      cin >> n;
      // memset(ans1, 0, sizeof ans1);
      // memset(ans2, 0, sizeof ans2);之前超时了一发
      for(int i = 1; i <= n; i ++){
        cin >> a[i];
        ans1[i] = ans2[i]  = 0; 
      }
      LL ans = 0;
      if(n & 1)
      {
        for(int i = 2; i < n; 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 {
         ans = 2e14;
         for(int i = 2; i < n; i += 2)
         {
           if(a[i] <= a[i - 1] || a[i] <= a[i + 1]){
            ans1[i] = max(a[i - 1], a[i + 1]) - a[i] + 1;
          }
           if(i > 2)ans1[i] += ans1[i - 2];
         }
         
         for(int i = 3; i < n; i += 2)
         {
           if(a[i] <= a[i - 1] || a[i] <= a[i + 1]){
            ans2[i] = max(a[i - 1], a[i + 1]) - a[i] + 1;
          }
           if(i > 3)ans2[i] += ans2[i - 2];
         }
         
         for(int i = 2; i < n; i += 2)
         {
           ans = min(ans, ans1[i] + ans2[n - 1] - ans2[i  + 1]);
         }
         ans = min(ans, min(ans1[n - 2], ans2[n - 1]));
      }
      cout << ans << endl;
    }
      
   
}