G 題面 定義\({{dp_i}_j}_k\)為考慮完第i個點，最左邊沒有染色的點為\(j\)，最右邊沒有染色的點為\(k\)的最小數量。 考慮轉移（用自己更新別人） 如果不用\(i\)，直接轉移到\({{dp_{i+1}}_j}_k\)。 如果向左噴，\(k\)為\(max({i+1,k})\)， ...
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;
}
