题解：CF407B Long Path

CF704B 题目传送门

题目大意

一天，小瓦西亚发现自己处于由

n+1

个房间组成的迷宫中，房间编号从

1

到

n+1

。起初，瓦西亚位于第一个房间，为了走出迷宫，他需要到达第

n+1

个房间。迷宫的组织方式如下。每个房间都有两个单向传送门。对于房间

i(1 \leq i \leq n)

，瓦西亚可以使用第一个传送门移动到房间

i+1

，或使用第二个传送门移动到房间

p_i (1 \leq p_i \leq i)

。

为了不迷失方向，瓦西亚决定采取以下行动：

每次进入一个房间，瓦西亚都会在房间的天花板上划一个十字。起初，他在第一个房间的天花板上划了一个十字。
如果房间 $i$ 的天花板上现有的十字数目是奇数，瓦西亚将使用第二个传送门（通向房间 $p_i$ ），否则使用第一个传送门。

帮助瓦西亚确定他需要使用传送门的次数，以便最终到达房间

n+1

。

解决思路

可以考虑 DP，一共有两种情况：

$dp_i=dp[i−1]+2$
$dp_i=dp[i−1]−dp[p_i−1]+2$

代码展示

CPP

#include <iostream>
using namespace std;

const int N = 1e3 + 10;
const int mod = 1e9 + 7;
int n, a[N], b[N], f[N];

int main()
{
	scanf("%d", &n);//建议scanf,更快
	for(int i = 1; i <= n; i++)
		scanf("%d", &b[i]);
	f[1] = a[1] = 2;
	for(int i = 2; i <= n; i++)
	{//DP
		f[i] = a[i - 1] - a[b[i] - 1] + 2;
		if(f[i] < 0) f[i] += mod;
		a[i] = a[i - 1] + f[i];
		a[i] %= mod;
	}
	printf("%d\n", a[n]);//建议printf,更快
	return 0;
}

题解：CF407B Long Path

文章操作

CF704B 题目传送门

题目大意

解决思路

代码展示

相关推荐

评论

题解：CF407B Long Path