做图片推广的网站,宁波超值关键词优化,自己想做个网站 费用,做app挣钱还是网站题意#xff1a;
起点为1#xff0c;终点为n1#xff0c;对应第i个各点#xff0c;如果我奇数次到达i点#xff0c;那么下一步走到a【i】的位子#xff0c;如果是偶数次到达#xff0c;那么下一步走到i1的位子。 问从1走到n1一共需要走多少步#xff1f;结果对1e97取模…题意
起点为1终点为n1对应第i个各点如果我奇数次到达i点那么下一步走到a【i】的位子如果是偶数次到达那么下一步走到i1的位子。 问从1走到n1一共需要走多少步结果对1e97取模。
题目
One day, little Vasya found himself in a maze consisting of (n 1) rooms, numbered from 1 to (n 1). Initially, Vasya is at the first room and to get out of the maze, he needs to get to the (n 1)-th one.
The maze is organized as follows. Each room of the maze has two one-way portals. Let’s consider room number i (1 ≤ i ≤ n), someone can use the first portal to move from it to room number (i 1), also someone can use the second portal to move from it to room number pi, where 1 ≤ pi ≤ i.
In order not to get lost, Vasya decided to act as follows.
Each time Vasya enters some room, he paints a cross on its ceiling. Initially, Vasya paints a cross at the ceiling of room 1. Let’s assume that Vasya is in room i and has already painted a cross on its ceiling. Then, if the ceiling now contains an odd number of crosses, Vasya uses the second portal (it leads to room pi), otherwise Vasya uses the first portal. Help Vasya determine the number of times he needs to use portals to get to room (n 1) in the end.
Input
The first line contains integer n (1 ≤ n ≤ 103) — the number of rooms. The second line contains n integers pi (1 ≤ pi ≤ i). Each pi denotes the number of the room, that someone can reach, if he will use the second portal in the i-th room.
Output
Print a single number — the number of portal moves the boy needs to go out of the maze. As the number can be rather large, print it modulo 1000000007 (109 7).
Examples
Input
2 1 2
Output
4
Input
4 1 1 2 3
Output
20
Input
5 1 1 1 1 1
Output
62
分析
1.定义状态dp[x][y]为从x走到y需要走多少次。 2.如果我们要到达某个点y则要到达y-1的点第一次到达y-1按照题目要求奇数次到达y-1点会到达s【y-1】所以第二次到达y-1,需从s【y-1】到达y-1故推出公式
dp【x】【y】dp【x】【y-1】【s【y-1】】【y-1】1
AC代码
#includestdio.h
#includestring.h
#includealgorithm
using namespace std;
const int M1e310;
const int mod1e97;
int dp[M][M],s[M];//设定dp【i】【j】表示从i走到j一共需要多少步。
int n;
void dfs(int x,int y)
{if(xy){dp[x][y]1;return ;}if(dp[x][y])return ;/**如果要到达y有两种情况第一次到达y-1回到s[i-1],在偶数次到达y-1时可直接到达y*/dfs(x,y-1);dfs(s[y-1],y-1);///考虑到s【i】i那么要想到i1这个格点去那么一定是从第i个格点走过去的。所以推出普遍公式dp[x][y]dp[x][y-1]dp[s[y-1]][y-1]1;/**那么x--y需要先第一次从x--y-1由规则到达【y-1】再从是【y-1】-y-1*/dp[x][y]%mod;
}
int main()
{while(~scanf(%d,n)){memset(dp,0,sizeof(dp));for(int i1; in; i)scanf(%d,s[i]);dfs(1,n1);printf(%d\n,dp[1][n1]-1);}return 0;
}
