NOJ 2364 时光的城堡(动态规划)
NOJ 2364 时光的城堡(动态规划)
NOJ 2364 时光的城堡
一、题目描述
时光公主住在魔法城堡中，松松骑士想去找心仪的时光，就必须要费一番功夫，而时光深谙魔法的机密，可以在城堡中自由穿梭。时光住的城堡中有𝑛+1间房间（标号从1开始），这些房间被赋予了魔法，如果松松第奇数次进入房间 𝑖 时，他会被传送到房间 𝑃𝑖 中（1≤𝑃𝑖≤𝑖）。如果松松是第偶数次进入房间 𝑖 ，那么他将进入到房间 𝑖+1 。这天松松惹时光生气了，时光进入了房间 𝑛+1 中，不想理松松。松松从房间1出发（把当前房间1看做第一次访问）， 请问松松要移动多少次才能进入房间 𝑛+1 挨打。
Input
第一行包括一个数字 𝑛(1≤𝑛≤100000)。
第二行包括𝑛个数字𝑃𝑖。
Output
输出一个整数，表示松松移动的次数，最后结果对 1𝑒9+7 取模。
Sample
Sample Input
2 1 2
Sample Output
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程序猿。 喜欢的话劳烦您动动小手点个赞~ 欢迎大家关注我奥~