看到 \(n \le 100\) 考虑 \(O(\text{poly}(n))\) dp。发现从左向右决策，因为一个点可以向左或向右覆盖，所以需要记最靠左的未覆盖的位置 \(j\) 和最靠右的已覆盖位置 \(k\)，状态就是 \(f_{i, j, k}\)，dp 最小的覆盖次数。
转移的讨论很简单。考虑不覆盖还是向左或向右覆盖，若向左或向右覆盖看能否覆盖到 \(j\) 或 \(k\)。这样转移是 \(O(1)\) 的。总时间复杂度 \(O(n^3)\)。
code
// Problem: G. Paint Charges
// Contest: Codeforces - Codeforces Round 923 (Div. 3)
// URL: https://codeforces.com/contest/1927/problem/G
// Memory Limit: 256 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 110;
int n, a[maxn], f[maxn][maxn][maxn];
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
mems(f, 0x3f);
f[0][1][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n + 1; ++j) {
for (int k = 0; k <= n; ++k) {
f[i][j][k] = min(f[i][j][k], f[i - 1][j][k]);
if (max(i - a[i] + 1, 1) <= j && j <= i) {
int nk = max(i, k);
f[i][nk + 1][nk] = min(f[i][nk + 1][nk], f[i - 1][j][k] + 1);
}
int nk = min(i + a[i] - 1, n);
if (nk > k) {
int nj = (i <= j && j <= nk ? nk + 1 : j);
f[i][nj][nk] = min(f[i][nj][nk], f[i - 1][j][k] + 1);
}
}
}
}
printf("%d\n", f[n][n + 1][n]);
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}