Codeforces 407B Long Path（好题 DP+思维）

题目链接：http://codeforces.com/problemset/problem/407/B

题目大意：
一共n+1个房间，一个人从1走到n+1，每次经过房间都会留下一个标记，每个房间有两扇门：
①第一扇门通向i+1,如果当前房间标记有奇数个，则必须走第一扇门。
②第二扇门通向pi(pi<=i),如果当前房间标记有偶数个，则必须走第二扇门。
问从房间1走到房间n+1需要多少步，结果对1e9+7取模。
解题思路：
之前傻了。。。明明都推出规律了，结果被自己给否定了。。。
设dp[i]表示从1~i需要走多少步，那么我们可以得到状态转移方程：
dp[i+1]=dp[i]+dp[i]-dp[p[i]]+2=2*dp[i]-dp[p[i]]+2
下面来解释一下，如果当前走到了i点，那么i点之前的所有点的标记数肯定都是偶数，因为只有标记为偶数才能往后走。
偶数可以看成是0，相当于跟第一次走一样。这里的2是因为从i到p[i]需要一步，从i到i+1需要一步。
从1~i为的步数为dp[i],然后返回p[i]，从p[i]~i的步数为dp[i]-dp[p[i]],所以总步数就是dp[i]+dp[i]-dp[p[i]]+2=2*dp[i]-dp[p[i]]+2。

代码

 #include<bits/stdc++.h>

 #define lc(a) (a<<1)

 #define rc(a) (a<<1|1)

 #define MID(a,b) ((a+b)>>1)

 #define fin(name)  freopen(name,"r",stdin)

 #define fout(name) freopen(name,"w",stdout)

 #define clr(arr,val) memset(arr,val,sizeof(arr))

 #define _for(i,start,end) for(int i=start;i<=end;i++)

 #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);

 using namespace std;

 typedef long long LL;

 const int N=1e5+;

 const int MOD=1e9+;

 const int INF=0x3f3f3f3f;

 const double eps=1e-;

 LL dp[N];

 int p[N];

 int main(){

     FAST_IO;

     int n;

     cin>>n;

     for(int i=;i<=n;i++){

         cin>>p[i];

     }

     for(int i=;i<=n;i++){

         dp[i+]=(*dp[i]-dp[p[i]]++MOD)%MOD;

     }

     cout<<dp[n+]<<endl;

     return ;

 }

巴特西

Codeforces 407B Long Path（好题 DP+思维）

最新文章

热门文章