1179: 上车人数(找规律解决问题）

解题思路:

站数       上车人数        下车人数        总人数

1              a                     0                 a

2              x                     x                 a

3              a+x                 x                2a

4              a+2x               a+x            2a+x

5              2a+3x             a+2x          3a+2x

6              3a+5x             2a+3x        4a+4x

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

我们观察总人数这一行就行，先看 a 的系数（ 1，1，2，2，3，4，6），从第四项开始，前两项的和-1=第三项，所以第一个数组 arr[1000]={1,1,2};

同理可得， x 的系数（0，0，0，1，2，4，7），从第四项开始，前两项的和+1=第三项，所以第二个数组 xrr[1000]={0,0,0},这样就可以动态规划了

注意事项:

参考代码:

#include<iostream>

using namespace std;

int main()

{

int a;//初始上车人数

int n;//终点站数

int m;//终点站人数

int x;//中途站

cin >> a >> n >> m >> x;

int arr[1000] = { 1,1,2 };// a 的系数变化

int xrr[1000] = { 0,0,0 };// x  的系数变化

int s1 = 0;

int s2 = 0;

for (int i = 3; i < n - 1; i++)//这里需要自己好好想想，理解题目 m 的含义，以及数组是如何存储元素的

{

arr[i] = arr[i - 1] + arr[i - 2] - 1;

xrr[i] = xrr[i - 1] + xrr[i - 2] + 1;

}

int x1 = (m - arr[n - 2] * a) / xrr[n - 2];//求出 x 的值

cout << arr[x - 1] * a + xrr[x - 1] * x1<<endl;//带入输出即可

return 0;

}