P1011 [NOIP 1998 提高组] 车站 题解

· · 题解

P1011 [NOIP 1998 提高组] 车站 题解

...其实可以打表

Code: 
#include <bits/stdc++.h>//由于我看不懂其他的题解 于是...模拟 
using namespace std;
int dp[25];//记录上车人数 
int main(){
    int a,n,m,x; cin >> a >> n >> m >> x;
    dp[1] = dp[2] = a;//上车人数都是前两站上车人数之和 -> 斐波那契 
    int in_last = a;//上一次的下车人数 
    int out = 0;    //当前下车人数 
    int in_now = 0; //上一次的上车人数 
    for(int i = 0;i <= 20;i++){//这一层是在枚举所有的站数 
        in_last = a,in_now = i,out = i;//保证不会被上一次情况所影响 
        dp[2] = a;
        for(int j = 3;j < n;j++){//从第3站到第n-1站 
            out = in_now;//当前下车人数=上一次上车人数 
            in_now += in_last;//更新为这一站的上车人数 
            in_last = out;//下一站的上车人数=这一站的下车人数 
            dp[j] = dp[j-1] + in_now - out;//当前车上的人数=上一站的车上人数+这一次上车人数-下车人数 
        }
        if(dp[n-1] == m) return cout << dp[x],0;//若第n-1站的车上人数=m,停止枚举 
    }
    return 0;
} 
/*
    规定t为第二站的上车人数 , dp[]为斐波那契的前几项 
    站点标号 上车人数 下车人数 车上人数 变化人数
        1       a         0        a       a
        2       t         a        a       0
        3      a+t        t        2a      a
        4      a+2t      a+t      2a+t     t
        5     2a+3t      a+2t     3a+2t   a+t
        6     3a+5t     2a+3t     4a+4t   a+2t
        7       0       4a+4t      0     4a+4t   假设7为最后一站 
        (...其实我们可以打表)
    我们发现:第x站的上车人数=dp[x-1]+dp[x-2]
             第x站的车上人数=第x-1站的车上人数+dp[x]-dp[x-1]  
*/

有些绕