P1135题解

思路

我写的好像是动规的做法。

设 \(f_{i,j}\) 表示第 \(i\) 步 \(j\) 个点是否可以走到，值要么为 \(1\)，要么为 \(0\)。最多走 \(n\) 步，因为总共只有 \(n\) 个点，每一步都肯定会多延伸出一个点，要不然就重复计算。

不难得出转移公式：

\(f_{i+1,j+k_j}=f_{i,j}\)
\(f_{i+1,j-k_j}= f_{i,j}\)

解释一下，因为只能从后往前，不然如果从当前往上一步就有需要一层循环。

注意：

• 第一个转移执行前提是 \(j+k_j \le n\)。
• 第二个转移执行前提是 $1 \le j- k_j $，如果不判断就会数组越界。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int f[205][205],n,a,b,k[205]; 
int main(){
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++)cin>>k[i];
	f[0][a]=1;
	for(int i=0;i<n;i++){
		for(int j=1;j<=n;j++){
			if(f[i][j]==0)continue;
			if(j+k[j]<=n){f[i+1][j+k[j]]=f[i][j];}
			if(j-k[j]>=1)f[i+1][j-k[j]]=f[i][j];
		}
	}
	for(int i=0;i<=n;i++){
		if(f[i][b]){
			cout<<i;
			return 0;
		}
	}
	cout<<-1;
	return 0;
}