洛谷 P2233 [HNOI]公交车线路

洛谷

不知道大家做没做过传球游戏，这一题和传球游戏的转移方程几乎一样。

令\(A\)为\(1\)点，\(E\)为\(5\)点，那么\(f[i][j]\)代表第i步走到j的方案数。

\[f[i][j]=f[i−1][j+1]+f[i−1][j−1]
\]

因为题中给的是一个环，所以有几种情况。

\[if(j==8)~f[i][j]=f[i−1][1]+f[i−1][7]
\]

\[if(j==1)~f[i][j]=f[i−1][8]+f[i−1][2]
\]

还有，因为题中说，到了\(E\)点，就不会再动了。

\[if(j==4)~f[i][j]=f[i−1][3]
\]

\[if(j==6)~f[i][j]=f[i−1][7]
\]

边界很显然\(f[0][1]=1\)。但是我们注意这一题\(n≤10^7\)，所以我们要滚动数组。

实际上我分析了一波，应该要用矩阵快速幂优化掉\(n\)那一维的，但是我交了一份递推代码上去也\(A\)了。

那么就不用管了，上代码：

#include <bits/stdc++.h>

using namespace std;

int main()

{

    int f[2][9]={},n,t=0;

    cin>>n;

    f[t][1]=1;

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

        t=!t;

        for (int j=1;j<=8;++j) {

            if (j==1) f[t][j]=f[!t][8]+f[!t][j+1];

            else if (j==8) f[t][j]=f[!t][j-1]+f[!t][1];

            else if (j==4) f[t][j]=f[!t][j-1];

            else if (j==6) f[t][j]=f[!t][j+1];

            else f[t][j]=f[!t][j-1]+f[!t][j+1];

            f[t][j]%=1000;

        }

    }

    cout<<f[t][5];

    return 0;

}

巴特西

洛谷 P2233 [HNOI]公交车线路

最新文章

热门文章