题解 | #附加题#

附加题

https://www.nowcoder.com/practice/58b04ed2865f4ff4921290f1bd4ee486

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);

        while(in.hasNext()){
            solution(in);
        }
    }

    /**
     * 动态规划
     * dp[i]: 第一次到达i房间的移动次数
     * 
     *         {   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]<i-1
     *         
     * @param in
     */
    private static void solution(Scanner in){
        int n = in.nextInt();
        int[] pi = new int[n+1];
        for(int i=1; i<=n; i++){
            pi[i] = in.nextInt();
        }

        long[] dp = new long[n+2];
        long mod = (long)(1e9+7);

        // 初始化
        dp[1] = 0;

        for(int i=2; i<=n+1; i++){
            if(pi[i-1] == i-1){
                dp[i] = dp[i-1]+2;
            }else if(pi[i-1] < i-1){
                dp[i] = dp[i-1]+(dp[i-1]-dp[pi[i-1]])+2;
            }
            dp[i] %= mod;
        }

        System.out.println(dp[n+1]<0?dp[n+1]+mod:dp[n+1]);
    }
}

全部评论

相关推荐

不要停下啊:大二打开牛客,你有机会开卷了,卷起来,去找课程学习,在牛客上看看大家面试笔试都需要会什么,岗位有什么需求就去学什么,努力的人就一定会有收获,这句话从来都经得起考验,像我现在大三了啥也不会,被迫强行考研,炼狱难度开局,啥也不会,找工作没希望了,考研有丝丝机会
点赞 评论 收藏
分享
零OFFER战士:另一个版本查看图片
点赞 评论 收藏
分享
小叮当411:应该是1-3个月吧
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务