本文主要是介绍CF - 407 - B. Long Path（dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：一个迷宫，有n+1个房间(1 ≤ n ≤ 1000) ，每个房间有2个门，第一个门通往i+1，第二个门通往pi（1 <= pi <= i），一个人，初始在房间1，他要走到房间n+1，每次他到一个房间，他就在房顶标记一次，然后他统计下他在这间房标记了多少次，如果是奇数，他会选择pi那个门，如果是偶数，他会选择i+1那个门，问他走到n+1房间时共走了多少次。
题目链接：http://codeforces.com/contest/407/problem/B
——>>他走到一间房子，标记一次，总记数为1，是奇数，于是他会选择往回的门走到pi，下次再到这个房间时，标记一次，总计数为2，偶数，前进，如果后面折回到这个房间，标一次，总计数变奇数，于是回折回pi，再次上来到这个房间时，总计数变偶数，往前。。可知，他每走过一个房间，就会将这个房间总计数变加偶数，就相当于初始状态没走过一样。
——>>如果直接模拟，考虑最坏情况，就是pi全为1的时候，一步步的标记统计模拟？？不忍吧。。
——>>按CF的题解：设d[i]表示从房间1到房间i需要走的步数，那么，要到房间i+1的话，只能从房间i走第1个门，但是第一次到房间i（需要d[i]步）时，根据上面的分析可知他会往回走到pi（需要1步），于是他要从pi到i（需要d[i]-d[pi]步），再从i到i+1（需要1步）。于是得状态转移方程为：
d[i+1] = d[i] + 1 + d[i] - d[pi] + 1 = 2d[i] + 2 - d[pi]。。
最后还是不小心WA了一次。。上面的式了有“-”号，取模运算后可能有负数出现。。所以。。T_T。。加上个模再取模吧。。
#include <cstdio>using namespace std;const int maxn = 1000 + 10;
const int mod = 1000000000 + 7;int main()
{int n, p[maxn];long long d[maxn];while(scanf("%d", &n) == 1) {d[1] = 0;for(int i = 1; i <= n; i++) {scanf("%d", p+i);d[i+1] = (2 * d[i] + 2 - d[p[i]] + mod) % mod;}printf("%I64d\n", d[n+1]);}return 0;
}
这篇关于CF - 407 - B. Long Path（dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
