【枚举】CF1706 C

有人一道1400写了一个小时

Problem - C - Codeforces

题意：

 

思路：

首先先去观察样例：

很显然，对于n是奇数的情况，只有一种情况，直接操作偶数位就好了

主要是没搞清楚n是偶数的情况

 

其实有个小技巧，在模拟样例的时候特殊化成0和1会比较好看一点

Code：

#include <bits/stdc++.h>#define int long longusing i64 = long long;using namespace std;const int N = 1e5 + 10;int h[N];int calc(int p) {if (h[p] > h[p - 1] && h[p] > h[p + 1]) return 0;else {return max({h[p - 1], h[p + 1]}) - h[p] + 1;}
}
void solve() {int n;cin >> n;for (int i = 1; i <= n; i ++) {cin >> h[i];}int ans = 0;for (int i = 2; i < n; i += 2) {ans += calc(i);}int res = ans;if (n % 2 == 0) {for (int i = n - 2; i >= 2; i -= 2) {res -= calc(i);res += calc(i + 1);ans = min(ans, res);}}cout << ans << "\n";
}
signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;cin >> t;while(t --) {solve();}return 0;
}