CodeForces 239 Long Path

March 31, 2014
DP CodeForce

每个房间有两个单向出口，就是只能进不能出，这个开始理解错了。

进入房间的时候，首先要在屋顶画一个叉叉，如果画完之后叉叉的个数是奇数的话：那么就从第二条出口出去，会到达ｐ[ i ]房间；如果叉叉的个数是偶数的话，那么就到下一个房间。

问从1到ｎ+1房间一共走了多少个这样的单项出口。

有一个条件：1 <= p[ i ] <= i 这个开始也没有注意到==。这是个很重要的条件。

说明人只能通过第二个出口向后退，而不能向前跳跃。如果人要向前走，只能一步一步的通过第一条出口。

所以，dp[ i ] 表示从i 房间到 i +1 房间需要经过的出口数。

还有一个特点：如果人第一次到房间 i ，那么他必定下一步到达房间p[ i ], 然后再考虑从房间p [ i ] 出发到达 p[ i +1] 房间。如果要到达i + 1房间。那么需要经过的出口数目就是：2 + dp[ p[i], p[i] + 1, … , i - 1 ] .其中的2 就是从房间 i 到房间p[ i ] 和从房间 i 到房间 i + 1的两步。另外一部分也就是从房间p[ i ] 到房间p[ i ] +1 ，从房间p[ i ] + 1 到房间 p[ i ] + 2等等。

代码：

/*
 * =====================================================================================
 *       Filename : LongPath.cpp
 *    Description : dp
 *    Version     : 0.1
 *        Created : 03/31/14 11:45
 *         Author : Liu Xue Yang (LXY), liuxueyang457@163.com
 *         Motto  : How about today?
 * =====================================================================================
 */
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;

/* 
 * ===  FUNCTION  ======================================================================
 *         Name: main
 * =====================================================================================
 */
int dp[1001], p[1001];
int MOD = 1000000000+7;
    int
main ( int argc, char *argv[] )
{
    int n;
    scanf ( "%d", &n );
//    printf ( "n = %d\n", n );
    for ( int i = 1; i < n + 1; ++i ) {
        scanf ( "%d", &p[i] );
//        printf ( "%d\n", p[i] );
    }
    fill(dp, dp + n + 1, 0);
    dp[1] = 2;
    for ( int i = 2; i < n + 1; ++i ) {
        dp[i] = 2;
        for ( int j = p[i]; j < i; ++j ) {
            dp[i] += dp[j];
            if ( dp[i] >= MOD ) {
                dp[i] -= MOD;
            }
        }
    }
    int sum = 0;
    for ( int i = 1; i < n + 1; ++i ) {
        sum += dp[i];
        if ( sum >= MOD ) {
            sum -= MOD;
        }
    }
    printf ( "%d\n", sum );

        return EXIT_SUCCESS;
}                /* ----------  end of function main  ---------- */

看的tourist的代码

Read more