Codeforces Round #239 (Div. 二)_Long Path
Codeforces Round #239 (Div. 2)_Long Path
题目链接
- 题意：
输入n个值，表示当前点与输入点（关联点）有一条边。初始从1开始，当到达一个点时，点值加一，如果此时值为奇数，那么将走到关联点，否则将到达右边相邻的点
求到达n+1时，要转移多少次 - 分析：
考虑一下第一次到达点P时候的情况，之前的每一个点的值肯定都是偶数（只能从之前的点过来，且只有在值为偶数时才能向右走）。此时因为当前点的值是奇数，所以会到达关联点Q（一定不在当前点的右侧），那么如果想到达下一个点，必须从点Q继续走到点P，而且这个时候的情况和从头走到点Q的情况完全一样（值为偶数和零显然是等价的），也就是得到了子问题 - 理解：
此题的状态转移虽然不是一个DAG，但是可以发现转移的时候是有条件的，而且从当前点往回找的时候只能到达之前的状态，所以可以考虑DP
同样的，DP的关键也在怎么样处理这个“环”
const int MAXN = 1100;
int ipt[MAXN], dp[MAXN];
int main()
{
// freopen("in.txt", "r", stdin);
int n;
while (~RI(n))
{
CLR(dp, 0);
FE(i, 1, n) RI(ipt[i]);
FE(i, 1, n)
{
dp[i + 1] = (2 * dp[i] % MOD + MOD + 2 - dp[ipt[i]]) % MOD;
}
WI(dp[n + 1]);
}
return 0;
}