CF1453F Even Harder

Description

https://www.luogu.com.cn/problem/CF1453F

Solution

首先，如果 $i$ 能到 $k$，则 $i$ 能到 $(i,k]$ 的任意一个点。

考虑从 $1\to n$ 开始的路径上的一段 $i\to j\to k$，则如果满足唯一一条路径，必须有 $(j,k)$ 中的任意一个点都不能到达 $k$。证明：如果存在点 $x$，则存在路径 $j\to x\to k$，就不是唯一一条路径了。

发现只跟当前到那里，路径的上一个点到哪里，于是可以 dp。令 $f_{i,j}$ 表示当前到 $i$ ，上一个点到的是 $j$。

考虑转移 $f_{i,j}\gets \min\limits_{r_k<i\le a_j} f_{j,k}+w(j+1,i-1)$。

$w(i,j)$ 显然可以 $O(n^2)$ 预处理出来，转移的话枚举 $j$，然后发现可以前缀 $\min$ 优化一下。复杂度 $O(n^2)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 3005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
const int inf=1e9;
int n;
int r[maxn],a[maxn],f[maxn][maxn],w[maxn][maxn],s[maxn];
void solve(void) {
	int i,j,ans=inf;
	read(n);
	for (i=0;i<=n+2;i++) for (j=0;j<=n+2;j++) f[i][j]=inf;
	for (i=1;i<=n;i++) read(a[i]),r[i]=min(n+1,i+a[i]);
	for (i=1;i<=n;i++) {
		w[i][i]=0;
		for (j=i-1;j>=0;j--) w[j][i]=w[j+1][i]+(r[j]>=i); 
	}
	f[1][0]=0;
	for (i=1;i<=n;i++) {
		for (j=0;j<=n+2;j++) s[j]=1e9;
		for (j=0;j<i;j++) s[r[j]+1]=min(s[r[j]+1],f[i][j]);
		for (j=1;j<=r[i];j++) s[j]=min(s[j-1],s[j]);
		for (j=i+1;j<=r[i];j++) {
			f[j][i]=w[i+1][j]+s[j];
		}
	}
	for (i=0;i<=n;i++) ans=min(ans,f[n][i]);
	printf("%d\n",ans);
}
signed main(void){
	int T;
	read(T);
	while (T--) solve();
	return 0;
}