CF1453F Even Harder 题解

来一个好想一点的状态。

首先“可达性”和

n\le 3000

让我们有这样一个思路：能不能从后往前 DP，状态里面加上“到达”、“路径”一类的东西？

还真的可以。

dp_{i,j}

表示考虑第

i

个格子能到达

n

，在唯一路径下的下一个格子是

j

，最少需要更改的数。

我们先考虑分析这条路径性质：假设这条路径经过格子

p_1

至

p_m

。有如下性质：

p_{i-2}+a_{p_{i-2}}<p_i

，显然的嘛。

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;
}
/*

*/

CF1453F Even Harder 题解

文章操作

相关推荐

评论

CF1453F Even Harder 题解