题解：CF407B Long Path

OIerJiang_1017 · 2024-12-13 16:13:57 · 题解

CF704B 题目传送门

题目大意

一天，小瓦西亚发现自己处于由 n+1 个房间组成的迷宫中，房间编号从 1 到 n+1。起初，瓦西亚位于第一个房间，为了走出迷宫，他需要到达第 n+1 个房间。迷宫的组织方式如下。每个房间都有两个单向传送门。对于房间 i(1 \leq i \leq n)，瓦西亚可以使用第一个传送门移动到房间 i+1，或使用第二个传送门移动到房间 p_i (1 \leq p_i \leq i)。

为了不迷失方向，瓦西亚决定采取以下行动：

• 每次进入一个房间，瓦西亚都会在房间的天花板上划一个十字。起初，他在第一个房间的天花板上划了一个十字。
• 如果房间 i 的天花板上现有的十字数目是奇数，瓦西亚将使用第二个传送门（通向房间 p_i），否则使用第一个传送门。

帮助瓦西亚确定他需要使用传送门的次数，以便最终到达房间 n+1。

解决思路

可以考虑 DP，一共有两种情况：

• dp_i=dp[i−1]+2
• dp_i=dp[i−1]−dp[p_i−1]+2

代码展示

#include <iostream>
using namespace std;

const int N = 1e3 + 10;
const int mod = 1e9 + 7;
int n, a[N], b[N], f[N];

int main()
{
    scanf("%d", &n);//建议scanf,更快
    for(int i = 1; i <= n; i++)
        scanf("%d", &b[i]);
    f[1] = a[1] = 2;
    for(int i = 2; i <= n; i++)
    {//DP
        f[i] = a[i - 1] - a[b[i] - 1] + 2;
        if(f[i] < 0) f[i] += mod;
        a[i] = a[i - 1] + f[i];
        a[i] %= mod;
    }
    printf("%d\n", a[n]);//建议printf,更快
    return 0;
}