B. Long Path dp

我就是我 2021-11-29 11:54 140阅读 0赞

[https://codeforces.com/problemset/problem/407/B][https_codeforces.com_problemset_problem_407_B]

这个题目是一个dp，有那么一点点的递归的意思，这个应该算一个找规律的dp，

dp\[i\]定义为第一次到第i个房间的步数，

转移方程 dp\[i\]=dp\[i-1\]+dp\[i-1\]-dp\[p\[i\]\]+1;

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    #include<string>
    #include<queue>
    #include<vector>
    #define inf 0x3f3f3f3f
    #define debug(x) cout<<"-----"<<" x = "<<x<<"-----"<<endl
    using namespace std;
    typedef long long ll;
    const int maxn = 5e3 + 10;
    const ll mod = 1e9 + 7;
    ll dp[maxn];
    int p[maxn];
    
    int main()
    {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
        dp[2] = 2;
        dp[1] = 0;
        for(int i=2;i<=n;i++)
        {
            dp[i+1] = (2 * dp[i]%mod - dp[p[i]]%mod + 2+mod)%mod;
        }
        printf("%lld\n", dp[n + 1]%mod);
        return 0;
    }

转载于:https://www.cnblogs.com/EchoZQN/p/10907129.html

[https_codeforces.com_problemset_problem_407_B]: https://codeforces.com/problemset/problem/407/B

发表评论取消回复

表情：

评论列表（有 0 条评论，140人围观）

还没有评论，来说两句吧...

相关阅读

相关【DP】ABC271 E - Subsequence Path

[E - Subsequence Path (atcoder.jp)][E - Subsequence Path _atcoder.jp] 题意：给定一个路径序列，请问1

客官°小女子只卖身不卖艺/ 2024年03月23日 11:21/ 0 赞/ 56 阅读

相关 dp Codeforces 429B B. Working out

B. Working out time limit per test 2 seconds memory limit per test 256 megabytes

以你之姓@/ 2022年08月19日 14:15/ 0 赞/ 12 阅读

相关 ZOJ Problem Set - 2563 Long Dominoes 【状压dp】

题目：[ZOJ Problem Set - 2563 Long Dominoes][] 题意：给出1\3的小矩形，求覆盖m\n的矩阵的最多的不同的方法数？

朱雀/ 2022年08月13日 00:53/ 0 赞/ 20 阅读

相关 leetcode 64. Minimum Path Sum DP动态规划

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom

逃离我推掉我的手/ 2022年06月09日 11:42/ 0 赞/ 175 阅读

相关 leetcode 63. Unique Paths II DP动态规划

Follow up for “Unique Paths”: Now consider if some obstacles are added to the grids. Ho

爱被打了一巴掌/ 2022年06月09日 11:42/ 0 赞/ 217 阅读

相关 leetcode 62. Unique Paths DP动态规划

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram

我不是女神ヾ/ 2022年06月09日 11:39/ 0 赞/ 170 阅读

相关【数位DP】B-number HDU - 3652

Think: 1知识点：数位DP 2题意：输入r，判断\[1, r\]区间内有多少个“wqb-number”，“wqb-number”的定义为数位内含有13且可以被13

朱雀/ 2022年06月08日 13:56/ 0 赞/ 182 阅读

相关 F. Graph Without Long Directed Paths

题目描述： You are given a connected undirected graph consisting of n vertices and m edge

刺骨的言语ヽ痛彻心扉/ 2022年02月25日 11:40/ 0 赞/ 138 阅读

相关 DP HDOJ 5492 Find a path

[题目传送门][Link 1] 题意：从(1, 1)走到(n, m)，每次往右或往下走，问(N\+M−1)∑(Ai−Aavg)2 的最小值分析：展开式子得到(N\+M−1

我不是女神ヾ/ 2021年12月23日 09:17/ 0 赞/ 189 阅读

相关 B. Long Path dp

[https://codeforces.com/problemset/problem/407/B][https_codeforces.com_problemset_proble

我就是我/ 2021年11月29日 11:54/ 0 赞/ 141 阅读