当前位置: 首页 > news >正文

[模拟赛] 过关(pass)

前言:

我做不出 \(T1\) 我活鸡蛋。/kk

题目描述:

\(n+1\) 关卡,有一个机器人从关卡 \(1\) 开始闯关,每个关卡里有一个陷阱。机器人没有第 \(i\) 关的经验时会回到第 \(pi\) 关重新闯一遍,并获得了这一关的经验。

有经验时机器人会直接到达下一关。由于机器人太笨了,所以通过一关后他会认为这一关的经验没用了,从而忘掉它。

请你算出机器人需要多少次才能到达终点?

解题思路:

设计状态 \(f_{i}\) 表示通过关卡 \(i\) 所需要的步数,那么从 \(i-1\)\(i\) 所经过的步骤应该是 \(i-1 \rightarrow i \rightarrow p_{i} \rightarrow i-1 \rightarrow i\)。所以转移应为 \(f_{i}=f_{i-1}+1+(f_{i-1}-f_{a_{i}}+1)\)

代码实现:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
int n, f[N];
signed main(){// freopen("pass.in", "r", stdin);// freopen("pass.out", "w", stdout);cin >> n;for(int i = 1, x; i <= n; i++) cin >> x, f[i] = f[i - 1] + 1 + (f[i - 1] - f[x - 1] + 1 + mod) % mod, f[i] %= mod;cout << f[n] << endl;return 0;
}
http://www.hskmm.com/?act=detail&tid=30296

相关文章:

  • 2025.10.13
  • 第十三节:基于 Redis+MQ+DB实现高并发秒杀下的扣减
  • c++初体验
  • 元宇宙的搜索引擎:如何在虚拟世界中查找信息 - 详解
  • 四则运算错题本和错题重做的建立
  • 行列式的性质
  • 04_SQL语句一
  • 死锁的原因、表现以排查
  • 详细介绍:【C++】二叉搜索树
  • 朱世乐的 Johnson 算法笔记
  • day010
  • 20232323 2025-2026-1《网络与系统攻防技术》实验一实验报告
  • 树莓派4B安装WiringPi使用gpio命令
  • 单调队列优化 dp
  • 1分钟Get宠物神兽壁纸我家猫被问疯了!
  • Zabbix 6.0+ 运用官方模板监控 Redis 数据库的完整安装指南
  • 【图论】Floyd算法简析
  • MyEclipse 2017 激活教程
  • 插入 dp
  • 05_Mysql与图片的存储
  • 【Linux】权限 - 实践
  • 斯坦福ACE框架:让AI自己学会写prompt,性能提升17%成本降87%
  • 【左扬精讲】SRE 别慌!我用 服务器监控指标 讲 KNN 分类算法,从相似度计算到异常识别,都是咱运维人能懂的话(含代码)
  • 博客园地址 - yuyue
  • 【终章】:幸福的复利——打造你的每日幸福微习惯 - 指南
  • 实用指南:Go 语言中的**数组 (Array)*用法
  • 行业词汇
  • Java实现业务数据报表的邮件定时发送功能
  • 编写Python自动化脚本,使用Autodesk Fusion辅助Ansys HFSS进行建模
  • 单 Pod DNS 记录(`web-0.nginx.default.svc.cluster.local`)排障与启用