P1011 [NOIP 1998 提高组] 车站

题目链接:

P1011 [NOIP 1998 提高组] 车站 - 洛谷

最佳思路:

枚举

#include<bits/stdc++.h> using namespace std; int main() { int a,n,m,x; cin >> a >> n >> m >> x; int up[25] = {0},down[25] = {0},sum[25] = {0}; up[1] = a,down[1] = 0,sum[1] = a; for (int i = 0 ; i < m;i++) { up[2] = i,down[2] = i,sum[2] = a; for(int j = 3;j < n;j++) { up[j] = up[j-1] + up[j - 2]; down[j] = up[j-1]; sum[j] = sum[j - 1] + up[j] - down[j]; } if(sum[n-1] == m) { cout << sum[x]; break; } } return 0; }

运用多个数组如up down sum记录状态

然后i开始枚举所有值,但i的上界是m：

因为可以推出人数是不断增加的

别忘记设置2车站的初始状态

然后循环模拟上下车直到n-1站

与目标值去对比即可

关键思想：用多组数组同步去记录某一时刻的各种状态

至少我老是想不起来这么用

和这个

P1003 [NOIP 2011 提高组] 铺地毯-CSDN博客

思想异曲同工