CodeForces 407B Long Path

本文主要是介绍CodeForces 407B Long Path，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

有n+1个格子  起点在1  每个格子有个前进1的门  前n个格子有个返回的门（返回前面某个格子）  奇数次走进一个格子就去走返回门  偶数次走前进门  问  走到n+1要走过几道门

思路：

一看就是DP

to[i]表示第i个格子的返回门

go[i]表示离开第i个格子需要的步数

sum[i]表示离开前i个格子需要的步数

明显  go[i]=sum[i-1]-sum[to[i]-1]+2  离开i点的步数为离开（从to[i]到i-1点）的步数和 + 第i个点返回门1步前进门1步

代码：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<string>
#include<map>
#include<set>
#include<queue>
using namespace std;
#define M 1010
#define mod 1000000007int go[M],sum[M],to[M];
int n;int main()
{int i,j;scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d",&to[i]);for(i=1;i<=n;i++){go[i]=(sum[i-1]-sum[to[i]-1]+2+mod)%mod;sum[i]=(sum[i-1]+go[i])%mod;}printf("%d\n",sum[n]);return 0;
}

这篇关于CodeForces 407B Long Path的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---