Solution
首先考虑最简单的情况，每次只杀栈底的怪物：
- 对于第 $1$ 个怪：需要 $h_1$ 刀。
- 对于第 $i(i \geq 2)$ 个怪：在第 $i - 1$ 个怪死后，它会掉 $1$ 点坠落伤害，于是就需要 $\max(0, h_i - 1)$ 刀。
此时的答案是 $\textrm{base} = h_1 + \sum_{i = 2} ^{n} \max(0, h_i - 1)$。
然后我们考虑提前杀掉第 $i(i \leq n - 1)$ 只怪的收益。
- 对于第 $i$ 只怪：本来需要 $h_i - 1$ 刀，现在需要 $h_i$ 刀，收益为 $-1$。
- 对于第 $i + 1$ 只怪：本来需要 $\max(0, h_{i + 1} - 1)$ 刀，现在需要 $\max(0, h_{i + 1} - i)$ 刀，收益为两者相减。
则净收益为 $\Delta_i = \max(0, h_{i + 1} - 1) - \max(0, h _{i + 1} - i) - 1$。
很自然地，我们想到 dp。但如果直接 dp 的话是有后效性的。多个位置一起提前杀，收益显然不是直接相加，而是会彼此影响。
这时候注意到一个结论：两个相邻的位置不能都被提前杀掉，否则一定不优。
证明：我们假设把 $i$ 和 $i + 1$ 都提前杀掉（记作 $\texttt{A}$），证明其一定劣于只提前杀 $i + 1$（记作 $\texttt{B}$）。
显然其只会影响到 $i, i + 1, i + 2$，我们分别来考虑。
- 对于 $i$：$\texttt{A}$ 需要 $h_i$ 刀，$\texttt{B}$ 现在需要 $h_i - 1$ 刀，$\texttt{A}$ 比 $\texttt{B}$ 多打 $1$ 刀。
- 对于 $i + 1$：$\texttt{A}$ 和 $\texttt{B}$ 相同，都是 $h_{i + 1}$ 刀。
对于 $i + 2$：对于 $\texttt{A}$，由于 $i$ 已经被杀掉了，所以杀 $i + 1$ 时 $i + 2$ 下面有 $i$ 个怪；对于 $\texttt{B}$，杀 $i + 1$ 时 $i + 2$ 下面有 $i + 1$ 个怪。
则 $\texttt{A}$ 比 $\texttt{B}$ 多打的刀数为 $\max(0, h_{i + 2} - i) - \max(0, h_{i + 2} - (i + 1))$ $\in \{0, 1\}$。
综上，$\texttt{A}$ 比 $\texttt{B}$ 多打 $1$ 或 $2$ 刀，所以 $\texttt{A}$ 劣于 $\texttt{B}$。
证毕。
令 $v_i = \max(0, \Delta_i)$，问题转化为：选不相邻的若干位置使得 $\sum v_i$ 最大。
于是就变成了简单 dp！设 $\textrm{dp}_{i, 1/0}$ 表示到 $i$ 为止且选/不选 $i$ 的最大收益。转移是简单的。
$$ \textrm{dp}_{i, 0} = \max(\textrm{dp}_{i - 1, 0}, \textrm{dp}_{i - 1, 1}) \\ \textrm{dp}_{i, 1} = \textrm{dp}_{i - 1, 0} + v_i $$
最后答案就是 $\textrm{base} - \max(\textrm{dp}_{n - 1, 0}, \textrm{dp}_{n - 1, 1})$。
Code
// Problem: D. Chicken Jockey
// Contest: Codeforces - Codeforces Round 1044 (Div. 2)
// URL: https://codeforces.com/contest/2133/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define rep(i, a, b) for(int (i) = (a); (i) <= (b); (i) ++)
#define per(i, a, b) for(int (i) = (a); (i) >= (b); (i) --)
#define ls x << 1
#define rs x << 1 | 1
using namespace std;
const int maxn = 2e5 + 5;
int n, h[maxn] ;
int v[maxn] ;
int f[maxn][2] ;
void solve(){
cin >> n ;
v[1] = 0 ;
rep(i, 1, n) f[i][0] = f[i][1] = 0 ;
rep(i, 1, n) cin >> h[i] ;
int base = h[1] ;
rep(i, 2, n) base += max(0ll, h[i] - 1) ;
rep(i, 2, n - 1) {
int delta = max(0ll, h[i + 1] - 1) - max(0ll, h[i + 1] - i) - 1 ;
v[i] = max(0ll, delta) ;
}
rep(i, 1, n - 1) {
f[i][0] = max(f[i - 1][0], f[i - 1][1]) ;
f[i][1] = f[i - 1][0] + v[i] ;
}
cout << base - max(f[n - 1][0], f[n - 1][1]) << endl ;
return ;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T = 1 ;
cin >> T ;
while(T -- ){
solve() ;
}
return 0 ;
}