标签搜索

目 录CONTENT

文章目录

字节--房间传送门.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 6 阅读 / 1,438 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

字节--房间传送门

@[toc]

一、题目描述

存在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:
4

例子说明1:
开始从房间1 只访问一次(访问1次房间1,即基数次)所以只能跳到p1,即:

房间1(访问次数+1,即访问房间1的次数为2,偶数次), 之后采用策略A跳到房间2,

房间2(访问1次房间2,即基数次)这时访问了一次因此采用策略B跳到房间2(房间2访问次数

+1,即偶数),之后采用策略A跳到房间3,

因此到达房间3需要 4 步操作。

二、分析

  •  仔细分析 1<=pi<=i 知道用动态规划做。
  •  因为pi的取值范围为1到i,说明在走到i房间时,如果需要传送,那么传送的房间位置要么就在当前房间,要么就在当前房间位置之前的房间
  •  因为传送只会后退,前进的唯一方式是偶数次到达某个房间后,+1到达下一个房间,不能跳跃
  •  所以如果成功到达i门,那么i门前面所有门都走过并且经过偶数次(偶数次并不是2次)(反正法也可以证明)
  •  如果当大imen,那么此时i门前面的所有门肯定是已经到达偶数次了
  •  如果到达i门需要移动的次数为dp[i],那么dp[i] = dp[i - 1] + 第二次到达i - 1 + 1;
  •  意思就是到达i门的移动次数等于到达i - 1门的移动次数 + 1;那么到达i - 1门的移动次数又怎么计算呢?到达i - 1门的移动次数就等于dp[i - 1] + 第二次到达i - 1的次数
  •  第一次到达i-1门后再走一步会回到p[i-1]此时p[i-1]门到达奇数次,其他所有门到达偶数次
  •  这和第一次到达p[i-1]门的情况完全相同,所以从p[i-1]门回到i-1门,需要dp[i-1]-dp[p[i-1]]
  •  所以dp[i] = dp[i-1] + dp[i-1] - dp[p[i-1]] + 1 + 1 ==》dp[i] = 2 * dp[i-1] - dp[p[i-1]] + 2

在这里插入图片描述

三、代码

#include <iostream>
using namespace std;
 
long long p[1001], dp[1001], n;
const long long mod = 1e9 + 7;
 
int main ()
{
    cin >> n;
    for (int i = 1; i<= n; ++i) 
    	cin >> p[i];
    	
    for (int i = 2; i <= n + 1; ++i)
        dp[i] = (2 * dp[i - 1] - dp[p[i - 1]] + 2) % mod;
        
    cout << (dp[n + 1] < 0 ? dp[n + 1] + mod : dp[n + 1]);
    return 0;
}
0

评论区