题目描述

火车从始发站（称为第1站）开出，在始发站上车的人数为a，然后到达第2站，在第2站有人上、下车，但上、下车的人数相同，因此在第2站开出时（即在到达第3站之前）车上的人数保持为a人。从第3站起（包括第3站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第n-1站），都满足此规律。现给出的条件是：共有N个车站，始发站上车的人数为a，最后一站下车的人数是m（全部下车）。试问x站开出时车上的人数是多少？

输入描述:

a( ≤ 20)， n( ≤ 20)， m( ≤ 2000)，和 x( ≤ 20)，

输出描述:

从x站开出时车上的人数。

示例1

输入
5 7 32 4
输出
13

解答

我用的也是递推，但是我总觉得我的递推和dalao们有些不同，于是就写了这篇题解

我们假设第二站上来的人数是x人，一直往下推：

第一站上了a人，车上剩a人

第二站上了x人，下了x人，车上剩a人

第三站上了a+x人，下了x人，车上剩2a人

第四站上了2x+a人，下了a+x人，车上剩2a+x人

第五站上了3x+2a人，下了2x+a人，车上剩3a+x人

以此类推

这是一个表：

车上人数-------车上人数------下车人数

1a+0x-----------0x+1a---------1x+0a

1a+0x-----------0x+1a---------1x+0a

2a+0x-----------1a+1x---------1x+0a

2a+1x-----------2x+1a---------1a+1x

3a+2x-----------3x+2a---------2x+1a

1a+4x-----------5x+3a---------3x+2a

6a+7x-----------8x+5a---------5x+3a

9a+12x---------13x+8a-------- 8x+5a

14a+20x-------21x+13a-------13x+8a

22a+33x-------34x+21a-------21x+13a

35a+54x-------55x+34a-------34x+21a

56a+88x-------89x+65a-------55x+34a

于是我们很容易发现

在某一站中剩的人数是（为自然数）

而从第四站开始就有了规律，及;

而则是;

所以，很明显当总站数或询问站数小于等于3时都需要特判，

而打出上面的表后，很容易就可以找到要输出的内容，这里不明确说明

而实现主要是先算出题目给出的总站数的两个系数然后用这条算式算出

而如果算出小数，说明不可行，输出"No answer."。

而如果可行，则再循环一次，算出询问站数的系数最后直接用就是结果了

注意，如果询问站数是最后一站，直接输出0，因为题目已明确表明在最后一站中人会下光；

还有，为了防止有人照套题解给出算式，我故意让某些变量重叠，请管理员们不要见怪。

代码： 
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
long long a,n,x,t1,t2,s1,s2,tt,ss;
double t,m;
int main()
{
    cin>>a>>n>>m>>x;
    if (n==x) {cout<<0<<endl;return 0;}
    if (x<=2||n<=3) {cout<<a<<endl;return 0;}
    if (x==3) {cout<<a*2<<endl;return 0;}
    t1=1;t2=2;s1=s2=0;
    for (int i=4;i<=n-1;i++)
    {    
        tt=t1;t1=t2;
        t2=tt+t2-1;    
        ss=s1;s1=s2;
        s2=ss+s2+1;    
    }    
    t=(m-t2*a)/s2;
    if (trunc(t)<t) {cout<<"No answer.";return 0;}
    t1=1;t2=2;s1=s2=0;
    for (int i=4;i<=x;i++)
    {    
        tt=t1;t1=t2;
        t2=tt+t2-1;    
        ss=s1;s1=s2;
        s2=ss+s2+1;    
    }    
    cout<<t2*a+s2*t;
    return 0;
}


来源：_wc_