CF407B Long Path 题解

huangqixuan / 2024-02-29 / 原文

Long Path 题解

https://www.luogu.com.cn/problem/CF407B

题意

一个人从一号房间出发,他每到大一个地方，会先标记一下,当前标记数为奇数时，他的下一个到达的房间时$p_i$,否则下一个到达的房间为$i + 1$,就求他从 $1$ 到 $n + 1$ 要移动几次。（初始，所有房间标记数为0）

化简后的题目,思路

无脑暴力思路：

模拟一遍。

有脑暴力思路：

每个房间的标记数只有奇偶两种状态。
第一次到达某个房间时要到达的下一个房间一定是$p_i$。
设当前在 $i$ 号房间，那么 $1,2 ...... i - 1$ 号房间的标记数一定为偶数。

对每个房间求这个房间的标记数从奇数变成偶数要移动几次。

输出 $n + 1$ 号房间要移动的次数。

AC思路

前缀和，记忆化。

记得取模！！！

时间复杂度

$O(n^2)$。

丑陋代码

#include <iostream>
#include <algorithm>

using namespace std;

const long long mod = 1e9 + 7;

int n, a[1010];
int l[1010], sum = 0, uuu;
long long ans[1010];

long long F(int x){
    if(sum != 0 && x == uuu + 1){
        return 0;
    }
    sum = 1;
    if(ans[x] >= 0){
        return (ans[x] + F(x + 1) + mod) % mod;
    }
    l[x]++, sum = 1;
    if(l[x] % 2 == 0){
        return (F(x + 1) + 1 + mod) % mod;
    }else{
        return (F(a[x]) + 1 + mod) % mod;
    }
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        ans[i] = -1;
    }
    ans[n + 1] = -1;
    for(int i = 1; i <= n + 1; i++){
        fill(l + 1, l + 2 + n, 0), uuu = i, sum = 0;
        ans[i] = F(i);
    }
    long long sum = 0;
    for(int i = 1; i <= n; i++){
        sum = (sum + ans[i] + mod) % mod;
    }
    cout << sum % mod;
    return 0;
}