洛谷P1011 [NOIP 98 提高组] 车站解答

斐波那契数列

题目描述

列车从起点站（即第1站）发车，此时有a名乘客登车。列车随后抵达第2站，在该站有乘客上下车，但上下车人数相等，因此列车在离开第2站时（即在驶向第3站之前），车内乘客数量仍保持为a人。从第3站开始（含第3站），上下车人数遵循特定规律：每站上车人数等于前两站上车人数之和，而下车人数则与上一站上车人数相等。此规律持续至终点站前一站（即第(n−1)站）。已知条件为：总共有n个车站，起点站上车人数为a，终点站下车人数为m（所有乘客均在此下车）。现要求计算列车在x站发车时的乘客数量？
对于所有测试案例，保证1≤ a ≤20，1≤ x ≤n ≤20，1 ≤ m ≤ 2×104。

输入格式

输入数据由一行四个整数构成，依次代表始发站的上车人数 a、途经的车站数量 n、终点站的下车人数 m 以及需要查询的站点编号 x。

    5 7 32 4
    
    
      
    

输出格式

请输出一个整数作为答案，该整数表示从 x 站发车时车厢内乘客的数量。

整体思路概述

我们可以先制作一张表格，其中a表示起点站的乘客数量，t表示第二站点上车的人数。

|上车人数|下车人数|车上增加人数|出站时人数||