#yyds干货盘点# 名企真题专题：附加题

haketest lv.1

发布时间：2022-12-22 08:22:42 269

相关标签： # java# java# 数据

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

输入：

2
1 2

输出：

说明：

开始从房间1 只访问一次所以只能跳到p1即 房间1， 之后采用策略A跳到房间2，房间2这时访问了一次因此采用策略B跳到房间2，之后采用策略A跳到房间3，因此到达房间3需要 4 步操作。

2.代码实现：

/**
 *         {   0                                i=1
 * dp[i] = {   dp[i-1]+2                        i>1,pi[i-1]=i-1
 *         {   dp[i-1]+(dp[i-1]-dp[pi[i-1]])+2  i>1,pi[i-1] */
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]);
    }
}

文章来源： https://blog.51cto.com/u_15488507/5937707

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。

#yyds干货盘点# 名企真题专题： 附加题

#yyds干货盘点# 名企真题专题：附加题