CF1453F Even Harder 题解
linjunye
·
·
题解
来一个好想一点的状态。
首先“可达性”和 n\le 3000 让我们有这样一个思路：能不能从后往前 DP，状态里面加上“到达”、“路径”一类的东西？
还真的可以。dp_{i,j} 表示考虑第 i 个格子能到达 n，在唯一路径下的下一个格子是 j，最少需要更改的数。
我们先考虑分析这条路径性质：假设这条路径经过格子 p_1 至 p_m。有如下性质：
$p_{i-1}+a_{p_{i-1}}\ge p_i$，这个是能走的条件。
对于编号为 $p_{i-1}+1$ 到 $p_i-1$ 的格子 $j$，$j+a_j<p_i$。
好的，现在我们开始转移：$dp_{i,j}=dp_{j,k}+cnt_{i,j}$。
$cnt_{i,j}$ 表示不满足第三条性质的格子数（即以下 $k$ 的个数：$i<j<k$ 且 $k+a_k\ge j$）。这个可以提前预处理，也可以 DP 过程中做，我更推荐提前做。
现在的问题是，$j$ 和 $k$ 的范围是多少？根据性质一和二，不难得出：$i+1\le j \le i+a_i$，$k>i+a_i$。
直接转移是 $O(n^3)$，你很快就能发现这可以直接后缀和优化，于是复杂度 $O(n^2)$。
难点依旧是在于状态，如果能想到去刻画路径，应该不难想到状态。
代码可能有一点细节，但不是很多。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3010;
const int mod=998244353;
const int INF=0x3f3f3f3f3f3f3f3f;
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
int n;
int a[N];
int cnt[N][N];
int dp[N][N];
int mn[N][N];
void solve(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int r=1;r<=n;r++){
cnt[r][r]=cnt[r-1][r]=0;
for(int l=r-2;l>=1;l--)cnt[l][r]=cnt[l+1][r]+(l+1+a[l+1]>=r);
}
for(int i=1;i<n;i++)for(int j=1;j<=n+1;j++)dp[i][j]=mn[i][j]=INF;
for(int j=1;j<=n+1;j++)dp[n][j]=mn[n][j]=0;
for(int i=n-1;i>=1;i--){
for(int j=i+1;j<=a[i]+i;j++)dp[i][j]=mn[j][i+a[i]+1]+cnt[i][j];
for(int j=n;j>=1;j--)mn[i][j]=min(mn[i][j+1],dp[i][j]);
}
cout<<mn[1][1]<<"\n";
return;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int Tc=1;
cin>>Tc;
while(Tc--)solve();
return 0;
}
/*
*/
```