407B


  Posted on 14 Dec 2014
dynamic programming

Solution


#include <cstdio>
using namespace std;

const int MAX_N = 1010;
const int MOD = int(1e9) + 7;

int n;
int back[MAX_N];
int f[MAX_N][MAX_N];

int main()
{
	//input
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &back[i]);
	}

	//work
	for (int i = 2; i <= n + 1; i++)
	{
		for (int j = i - 1; j >= 1; j--)
		{
			f[j][i] = 0;
			f[j][i] = (f[j][i] + f[j][i - 1]) % MOD;
			f[j][i] = (f[j][i] + f[back[i - 1]][i - 1]) % MOD;
			f[j][i] = (f[j][i] + 2) % MOD;
		}
	}
	printf("%d\n", f[1][n + 1]);
	return 0;
}