3
#yyds干货盘点# 解决名企真题：附加题
source link: https://blog.51cto.com/u_15488507/5470324
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# 解决名企真题：附加题
原创1.简述：
描述
存在n+1个房间，每个房间依次为房间1 2 3...i，每个房间都存在一个传送门，i房间的传送门可以把人传送到房间pi(1<=pi<=i),现在路人甲从房间1开始出发(当前房间1即第一次访问)，每次移动他有两种移动策略： A. 如果访问过当前房间 i 偶数次，那么下一次移动到房间i+1； B. 如果访问过当前房间 i 奇数次，那么移动到房间pi；现在路人甲想知道移动到房间n+1一共需要多少次移动；
输入描述：
第一行包括一个数字n(30%数据1<=n<=100，100%数据 1<=n<=1000)，表示房间的数量，接下来一行存在n个数字 pi(1<=pi<=i), pi表示从房间i可以传送到房间pi。
输出描述：
输出一行数字，表示最终移动的次数，最终结果需要对1000000007 (10e9 + 7) 取模。
示例1
开始从房间1 只访问一次所以只能跳到p1即 房间1， 之后采用策略A跳到房间2，房间2这时访问了一次因此采用策略B跳到房间2，之后采用策略A跳到房间3，因此到达房间3需要 4 步操作。
2.代码实现：
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
// 1-n
int[] pi = new int[n + 1];
// 1-(n+1)
long[] dp = new long[n + 2];
// 1-n
for(int i = 1; i <= n; ++i){
pi[i] = sc.nextInt();
}
sc.close();
long mod = (long)(1e9+7);
// 2-(n+1)
for(int i = 2; i <= n + 1; ++i){
if(pi[i - 1] == i - 1){
dp[i] = (dp[i - 1] + 2) % mod;
}else{
dp[i] = (dp[i - 1] + (dp[i - 1] - dp[pi[i - 1]]) + 2) % mod;
}
}
// System.out.println(Arrays.toString(dp));
System.out.println(dp[n + 1] < 0 ? dp[n + 1] + mod : dp[n + 1]);
}
}
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
// 1-n
int[] pi = new int[n + 1];
// 1-(n+1)
long[] dp = new long[n + 2];
// 1-n
for(int i = 1; i <= n; ++i){
pi[i] = sc.nextInt();
}
sc.close();
long mod = (long)(1e9+7);
// 2-(n+1)
for(int i = 2; i <= n + 1; ++i){
if(pi[i - 1] == i - 1){
dp[i] = (dp[i - 1] + 2) % mod;
}else{
dp[i] = (dp[i - 1] + (dp[i - 1] - dp[pi[i - 1]]) + 2) % mod;
}
}
// System.out.println(Arrays.toString(dp));
System.out.println(dp[n + 1] < 0 ? dp[n + 1] + mod : dp[n + 1]);
}
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK