清楚姐姐跳格子
题目背景
题目描述
样例 #1
样例输入 #1
5
2 3 1 5 4
样例输出 #1
2
做题思路
首先知道
a
i
≥
1
a_i \ge 1
ai≥1，所以必定有一个正整数因子1
至少可以从第一格一步步的到达第
n
n
n格，所以答案肯定是有的。
假定
v
i
s
i
vis_i
visi为从第
i
i
i格到第
n
n
n格的最少步数。
那么初始化为
for(int i=1;i<=n;i++)cin >> a[i] , vis[i] = n-i;
后面考虑假如一直往右跳的可能。
这时候从前往后遍历的话会导致前面用了后面的 v i s vis vis但该 v i s vis vis并不是真正的从第 i i i格到第 n n n格的最少步数。
所以考虑从后往前遍历，这样遍历到前面用后面的 v i s vis vis就是一直往右跳真正的从第 i i i格到第 n n n格的最少步数。
这时就产生了第一个“状态转移“方程vis[i] = min(vis[i],vis[i+k]+1)
其中
k
k
k为
a
i
a_i
ai的一个正整数因子。
现在再考虑又往右又往左的情况。
实际上就是假如该点的
v
i
s
i
vis_i
visi变了，那么依附于其(或者“状态转移“方程出现
v
i
s
i
vis_i
visi)的
v
i
s
j
vis_j
visj全都得变。
简单来说就是当第 i i i个格子的 v i s i vis_i visi(为从第 i i i格到第 n n n格的最少步数)变少了，那么如果存在一个 j j j并且第 j j j个格子能跳到第 i i i个格子那么该格子的 v i s j vis_j visj就可能变少。
如果 v i s j vis_j visj变少，只可能变成 v i s i + 1 vis_i + 1 visi+1,因为现在是 v i s i vis_i visi变少了，更新完 v i s i vis_i visi后需要检查 v i s j vis_j visj需不需要更新
其状态转移方程为 v i s j = min ( v i s i + 1 , v i s j ) vis_j = \min{(vis_i+1,vis_j)} visj=min(visi+1,visj)
同理如果 v i s j vis_j visj变少也需要重复以上操作。
总结：
本题核心为vis[i] = min(vis[i],vis[i+k]+1)
因为该方程不满足无后效性，所以使用dfs进行关联更新
代码
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <tuple>
#include <cstring>
#include <cmath>
#define int long long
using namespace std;
const int N = 1e5+10;
const int INF = 0x3f3f3f3f3f3f3f3f;
vector<vector<int>>connect(N,vector<int>());
int vis[N] , n , a[N];
void dfs(int x){
for(auto j :connect[x]){
if(vis[j] > vis[x]+1){
vis[j] = vis[x] + 1;
dfs(j);
}
}
}
signed main(){
cin >> n;
for(int i=1;i<=n;i++)cin >> a[i] , vis[i] = n-i;
for(int i=n-1;i>=1;i--){
int x = a[i] , u = i;
for(int j=1;j<=x/j;j++){
if(j > n)break;//注意重点剪枝，大于n必定跳出格子
if(x%j == 0){
int k1 = j , k2 = x/j;
if(k1 + u <= n && k1 + u >= 1 && vis[k1+u] + 1 < vis[u]){
vis[u] = vis[k1 + u] + 1;
connect[u+k1].push_back(i);
}
if(u - k1 >= 1 && u - k1 <= n){
vis[u] = min(vis[u],vis[u - k1] + 1);
connect[u-k1].push_back(i);
}
if(k2 + u <= n && k2 + u >= 1 && vis[k2+u] + 1 < vis[u]){
vis[u] = vis[k2 + u] + 1;
connect[k2+u].push_back(i);
}
if(u - k2 >= 1 && u - k2 <= n){
vis[u] = min(vis[u - k2] + 1,vis[u]);
connect[u-k2].push_back(i);
}
}
}
dfs(i);
//for(int i=1;i<=n;i++)cout << vis[i] << " \n"[i==n];
}
cout << vis[1];
return 0;
}