时光公主住在魔法城堡中,松松骑士想去找心仪的时光,就必须要费一番功夫,而时光深谙魔法的机密,可以在城堡中自由穿梭。时光住的城堡中有𝑛+1间房间(标号从1开始),这些房间被赋予了魔法,如果松松第奇数次进入房间 𝑖 时,他会被传送到房间 𝑃𝑖 中(1≤𝑃𝑖≤𝑖)。如果松松是第偶数次进入房间 𝑖 ,那么他将进入到房间 𝑖+1 。这天松松惹时光生气了,时光进入了房间 𝑛+1 中,不想理松松。松松从房间1出发(把当前房间1看做第一次访问), 请问松松要移动多少次才能进入房间 𝑛+1 挨打。
第一行包括一个数字 𝑛(1≤𝑛≤100000)。
第二行包括𝑛个数字𝑃𝑖。
输出一个整数,表示松松移动的次数,最后结果对 1𝑒9+7 取模。
2 1 2
4
首先是穷举的思路,而由于每次会回头重新来过,在最差情况下(假设每次退回到房间1),如果跟着松松的步伐不断走下去,那么复杂度将是2n,而n已经到了10,0000级别,所以用这种算法直接去Pending,必定TLE(用Py3算了一下,复杂度最坏已经达到约9×103,0103次,非常恐怖)。
因此,这个题不能使用暴力穷举的方法进行解答。那该怎么办呢?我们不妨实验一下:假设从开头房间1,一直走到第一次进入房间n+1所需要的步数是sum[n]
,那么sum[n]
要怎么算呢?我们不难发现:
sum[n] = sum[n-1] + 从第一次进房间n 到 第一次进入房间n+1 的步数
忽略求模运算,从第一次进房间n 到 第一次进入房间n+1 的步数
是多少?当Pi = i时,只需要2步即可;当 Pi != i 时,则需要回退的1步+(sum[i-1] - sum[p[i]-1])+前进的1步即可。即为2 + sum[i-1] - sum[p[i]-1]
,至此我们发现所有的问题都可以转化到sum子问题上,可见具有最优子结构(大问题依赖小问题的解)和重叠子问题(很可能重复多次用到sum[k])的性质,并且状态转移方程已经明确,故选择DP。
题解C++代码如下:
#include <cstdio>
using namespace std;
const int mod=1e9 + 7;
int n;
long long cur;
long long p[110000];
long long sum[110000];
int main(int argc, const char * argv[]) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld",&p[i]);
}
// 设从房间1开始,跳入房间k+1间的时候需要的总步数为sum[k]
sum[1] = 2;
for (int i = 2; i <= n; i++) {
if(p[i] == i) {
cur = 2;
} else {
cur = (2+sum[i-1]+mod-sum[p[i]-1])%mod;
}
sum[i] = (sum[i-1]+cur)%mod;
}
printf("%lld\n", sum[n]%mod);
return 0;
}
我叫小博,来自小破邮, 是一个喜欢算法的Java程序猿。 喜欢的话劳烦您动动小手点个赞~ 欢迎大家关注我奥~