题解 P2233 【[HNOI2002]公交车路线】

· · 题解

极度简洁的DP做法

我们把E去掉，这个系统分成了以A为中心的完全对称的列

我们记dp[i][j]表示第i站在j次乘坐后到达的方案数

因为每次只能从相邻的站到达，那么第N次到达E的方案数等于第N-1次到达D和F的方案数

以此类推dp[i][j]=dp[i-1][j-1]+dp[i+1][j-1] 这里的i-1，i+1表示相邻的站

之前说过以A为中心完全对称，所以D和F，C和G......的方案数完全相同，只需算一边

仔细观察，每个状态只与上一个状态有关，因此可以压位为dp[4][2]

代码如下：

#include<iostream>
using namespace std;
int dp[4][2];              //具体含义如上所述
int main()
{
    fill(dp[0],dp[0]+4*2,0);
    dp[0][0]=1;
    int N,pos=0;
    cni>>N;
    for(int k=1;k<N;k++)
    {
        pos=pos^1;
        dp[0][pos]=2*dp[1][pos^1]%1000;        //A处的方案等于两边的方案相加，由于相等只算一边的*2
        dp[1][pos]=(dp[0][pos^1]+dp[2][pos^1])%1000;
        dp[2][pos]=(dp[1][pos^1]+dp[3][pos^1])%1000;
        dp[3][pos]=dp[2][pos^1];                     //D只能由C来
    }
    cout<<2*dp[3][pos]%1000<<endl;            //E由D和F来
    return 0;        
}