G
题面
定义\({{dp_i}_j}_k\)为考虑完第i个点，最左边没有染色的点为\(j\)，最右边没有染色的点为\(k\)的最小数量。
考虑转移（用自己更新别人）
如果不用\(i\)，直接转移到\({{dp_{i+1}}_j}_k\)。
如果向左喷，\(k\)为\(max({i+1,k})\)，判断能喷到的位置
- 比\(j\)更靠左，\(j\)将变成\(max({i+2,k+1})\)（\(i+1\)的下一个或\(k\)的下一个将为最左边没有染色的）；
- 否则，\(j\)将不变。
如果向右喷，\(k\)为\(max({i+a_i-1,k})\)，判断能喷到的位置
- 比\(j\)更靠左，\(j\)将变成\(max({i+a_i,k+1})\)（\(i+a_i-1\)的下一个或\(k\)的下一个将为最左边没有染色的）；
- 否则，\(j\)将不变。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
int n;
int a[105];
int q[105];
int h[105];
int dp[105][105][105];
void mx(int &a,int b){
a = min(a,b);
}
void qwq(){
cin >> n;
for(int i = 1;i <= n;++ i){
cin >> a[i];
q[i] = max(1ll,i-a[i]+1);
h[i] = min(n,i+a[i]-1);
}
memset(dp,0x3f,sizeof(dp));
dp[0][1][0] = 0;
for(int i = 0;i < n;++ i){
for(int j = 1;j <= n+1;++ j)
for(int k = 0;k <= n;++ k)
mx(dp[i+1][j][k],dp[i][j][k]);
for(int j = 1;j <= n+1;++ j){
for(int k = 0;k <= n;++ k){
if(q[i+1] <= j){
mx(dp[i+1][max(i+2,k+1)]
[max(i+1,k)],dp[i][j][k]+1);
}
else{
mx(dp[i+1][j][max(i+1,k)],
dp[i][j][k]+1);
}
}
}
for(int j = 1;j <= n+1;++ j){
for(int k = 0;k <= n;++ k){
if(i+1 <= j){
mx(dp[i+1][max(h[i+1]+1,j)]
[max(h[i+1],k)],
dp[i][j][k]+1);
}
else{
mx(dp[i+1][j][max(h[i+1],k)]
,dp[i][j][k]+1);
}
}
}
}
cout << dp[n][n+1][n] << endl;
}
signed main(){
cin >> t;
while(t--) qwq();
return 0;
}