本文主要是介绍洛谷P2233公交车路线，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
在长沙城新建的环城公路上一共有 88 个公交站，分别为 A、B、C、D、E、F、G、H。公共汽车只能够在相邻的两个公交站之间运行，因此你从某一个公交站到另外一个公交站往往要换几次车，例如从公交站 A 到公交站 D，你就至少需要换 33 次车。
Tiger 的方向感极其糟糕，我们知道从公交站 A 到公交 E 只需要换 44 次车就可以到达，可是 tiger 却总共换了n 次车，注意 tiger 一旦到达公交站 E，他不会愚蠢到再去换车。现在希望你计算一下 tiger 有多少种可能的乘车方案。
输入格式
仅有一个正整数 n，表示 tiger 从公交车站 A 到公交车站 E 共换了 n 次车。
输出格式
输出一个正整数表示方案数，由于方案数很大，请输出方案数除以 10001000 后的余数。
输入样例
说明/提示
8 条路线分别是：
(A→B→C→D→C→D→E)，(A→B→C→B→C→D→E)，
(A→B→A→B→C→D→E)，(A→H→A→B→C→D→E)，
(A→H→G→F→G→F→E)，(A→H→G→H→G→F→E)，
(A→H→A→H→G→F→E)，(A→B→A→H→G→F→E)。
数据范围
4≤n≤。
极度简洁的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处的方案等于两边的方案相加，由于相等只算一边的*2dp[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;
}记得点赞哟！
这篇关于洛谷P2233公交车路线的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
