题解：洛谷 P2233 [HNOI2002] 公交车路线

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P2233 [HNOI2002] 公交车路线【题目描述】在长沙城新建的环城公路上一共有8 88个公交站分别为 A、B、C、D、E、F、G、H。公共汽车只能够在相邻的两个公交站之间运行因此你从某一个公交站到另外一个公交站往往要换几次车例如从公交站 A 到公交站 D你就至少需要换3 33次车。Tiger 的方向感极其糟糕我们知道从公交站 A 到公交 E 只需要换4 44次车就可以到达可是 tiger 却总共换了n nn次车注意 tiger 一旦到达公交站 E他不会愚蠢到再去换车。现在希望你计算一下 tiger 有多少种可能的乘车方案。【输入】仅有一个正整数n nn表示 tiger 从公交车站 A 到公交车站 E 共换了n nn次车。【输出】输出一个正整数表示方案数由于方案数很大请输出方案数除以1000 10001000后的余数。【输入样例】6【输出样例】8【核心思想】问题分析给定8 88个公交站环形排列A~H编号0 00~7 77相邻站之间有直达路线。Tiger 从 A 站编号0 00出发恰好换乘n nn次后到达 E 站编号4 44且一旦到达 E 站就不再换乘。求方案数对1000 10001000取模。这是一个线性 DP问题核心在于状态转移时排除从 E 站出发的路径吸收态。算法选择一维线性 DP滚动数组f [ i ] [ j ] f[i][j]f[i][j]表示换乘i ii次后到达第j jj个站的方案数环形邻接每个站j jj的相邻站为( j − 1 8 ) % 8 (j-18) \% 8(j−18)%8和( j 1 ) % 8 (j1) \% 8(j1)%8A 和 H 也相邻吸收态处理到达 E 站编号4 44后停止因此 E 站不能作为转移来源关键步骤初始化f [ 0 ] [ 0 ] 1 f[0][0] 1f[0][0]1换乘0 00次在 A 站1 11种方案其余为0 00DP 递推i ii从1 11到n nn使用滚动数组c u r i % 2 cur i \% 2curi%2p r e ( i − 1 ) % 2 pre (i-1) \% 2pre(i−1)%2遍历当前站j jj0 00到7 77计算左右邻站l e f t ( j − 1 8 ) % 8 left (j-18) \% 8left(j−18)%8r i g h t ( j 1 ) % 8 right (j1) \% 8right(j1)%8状态转移f [ c u r ] [ j ] ( f [ p r e ] [ l e f t ] ⋅ [ l e f t ≠ 4 ] f [ p r e ] [ r i g h t ] ⋅ [ r i g h t ≠ 4 ] ) m o d 1000 f[cur][j] (f[pre][left] \cdot [left \neq 4] f[pre][right] \cdot [right \neq 4]) \bmod 1000f[cur][j](f[pre][left]⋅[left4]f[pre][right]⋅[right4])mod1000其中[ c o n d i t i o n ] [condition][condition]为指示函数排除从 E 站转移来的路径输出答案f [ n % 2 ] [ 4 ] f[n \% 2][4]f[n%2][4]换乘n nn次后到达 E 站的方案数时间/空间复杂度时间复杂度O ( n × 8 ) O ( n ) O(n \times 8) O(n)O(n×8)O(n)每次换乘枚举8 88个站每个站O ( 1 ) O(1)O(1)转移空间复杂度O ( 8 ) O ( 1 ) O(8) O(1)O(8)O(1)滚动数组仅维护两行线性 DP 的核心思想状态定义清晰f [ i ] [ j ] f[i][j]f[i][j]精确刻画换乘i ii次后在j jj站的方案数满足无后效性吸收态建模E 站作为终点到达后不再离开通过禁止从 E 站向其他站转移实现而非将 E 站方案数清零因为需要统计最终到达 E 站的方案环形结构处理取模运算( j ± 1 8 ) % 8 (j \pm 1 8) \% 8(j±18)%8优雅处理 A-H 的环形邻接滚动数组优化由于f [ i ] f[i]f[i]仅依赖f [ i − 1 ] f[i-1]f[i−1]用两行数组交替使用将空间从O ( n ) O(n)O(n)降至O ( 1 ) O(1)O(1)适用于环形图上的路径计数、带吸收态的随机游走、有限状态转移类问题【算法标签】#普及 #线性DP-一维【代码详解】#includebits/stdc.husingnamespacestd;constintN10000005,mod1000;// N:最大换乘次数上限, mod:取模基数intf[2][8];// 滚动数组f[cur][j]表示换乘i次后到达第j个公交站0A,1B,...,4E,...,7H的方案数intn;// tiger实际换乘的次数intmain(){cinn;// 读入换乘次数f[0][0]1;// 初始状态换乘0次时在A站编号0方案数为1for(inti1;in;i)// 外层循环枚举每次换乘{intcuri%2;// 当前轮次的数组下标滚动数组优化空间intpre(i-1)%2;// 上一轮次的数组下标for(intj0;j8;j)// 内层循环枚举当前所在的公交站0~7对应A~H{// 计算当前站j的左右相邻站环形结构A和H也相邻intleft(j-18)%8,right(j1)%8;intsum0;// 累加到达当前站的方案数// 可以从左邻站到达当前站但不能从E站编号4转移到达E就停止if(left!4)sumf[pre][left];// 可以从右邻站到达当前站同样不能从E站转移if(right!4)sumf[pre][right];f[cur][j]sum%mod;// 对1000取模存储}}// 输出换乘n次后到达E站编号4的方案数coutf[n%2][4]endl;return0;}【运行结果】6 8