洛谷 P1011 车站

　　提供两种解法，第一种解法利用递推公式（借鉴dingcx的代码），第二种解法则是利用枚举依次列举出来，如果符合条件的话便输出答案

1.递推：根据题意可列出一个表格

由于第2站上车的人数是未知的，暂且将其设成 t，那么由表格可得出相应的规律，如第一行和第二行从某一列开始，a 和 t 的系数便是前面两项的相加之和，

相应的，我们猜测第三行也具有类似的规律，观察发现从第四列开始，a 和 t 的系数分别为前两个表达式中a系数的和 -1 和t系数的和 +1，因此便可以得出在某一站点时的人数，

设 a 和 t 的值为 index1[ i ]和index2[ i ]

index1[i]= index1[i-1] + intex1[i-2]-1;//前两个的和-1

index2[i]= index2[i-1] + index2[i-2]+1; //和+1

在这之后，t的值也能算出来了，由于m=

由于最后一站（第 n 站）不会有人上车，车上的人都下去，那么第n站的人数也就是第n - 1站出发时车上的人数。

下面是代码：

 1 #include <stdio.h>
 2 int index1[21]index2[21];
 3 int a, n, m, x;
 4 int main(){
 5     scanf("%d %d %d %d",&a,&n,&m,&x);
 6     index[2] = 1;
 7     index[3] = 2;
 8     for(int i = 4; i <= n; i ++){
 9         index[i] = index[i - 1] + index[i - 2] - 1;
10         index[i] = index[i - 1] +index[i - 2] + 1;
11     }
12     int b = (m - a*index1[n - 1]) / index2[n - 1];
13     printf("%d
",a*index1[x] + b*index2[x]);
14     return 0;
15 }

第二种利用枚举法：

从第2站开始，设其上车和下车的人数都是num,则从前往后由0开始枚举，当到最后一站时车上人数和m相等便符合题意。

 1 #include <stdio.h>
 2 int up[1000],down[1000],last[1000];
 3 int a, n, m, x;
 4 int main(){
 5     scanf("%d %d %d %d",&a,&n,&m,&x);
 6     up[1] = a;
 7     down[1] = a;
 8     for(int i = 0; ; i ++){
 9         up[2] = i;
10         last[2] = i;
11         for(int j = 3;j <= n - 1; j ++){
12             up[j] = up[j - 1] + up [j - 2];
13             down[j] = up[j - 1];
14             last[j] = last[j - 1] + up[j] - down[j];
15         }
16         if(last[i] == m){
17             printf("%d
",last[x]);
18             break;
19         }
20     }
21     return 0;
22 }