题解 P1011 【车站】

__Chtholly · 2019-12-15 22:45:10 · 题解

车站 p1011思路 首先推导一下这一题的解题思路： 第一次上车人数=a，下车=0； 第二次上车人数=y，下车=y； 第三次上车人数=y+a，下车=y； 第四次上车人数=2y+2,下车=y+a; 现在，我们已经找到了重要的题解方法 上车y的人数=前一次y的人数+前二次y的人数 所以求得以下的东西： 第一次上车：a 第二次上车：0 第三次（开始变懒）：a 第四次：y 第五次：y+a 第六次：2y+a 从第五个开始，上车人数有了规律：d[i][y]=d[i-1][y]+d[i-2][y] d[i][a]=d[i-1][a]+d[i-2][a] 找完规律后，直接贴代码：

#include<bits/stdc++.h>
using namespace std;
#define N 10005
template <typename _tp> inline _tp in(_tp&x){
    char ch=getchar(),sgn=0;x=0;
    while(ch^'-'&&!isdigit(ch))ch=getchar();if(ch=='-')ch=getchar(),sgn=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();if(sgn)x=-x;return x;
}//输入为in(变量)就可以了,但是一次只能输入一个qwq
int d[N][2],a,n,m,x,people;
void derive(int cs)//推导公式过程 
{
    d[1][1]=1;d[1][2]=0;d[2][1]=0;d[2][2]=0;d[3][1]=1;d[3][2]=0;d[4][1]=0;d[4][2]=1;int i=5;
    if(cs<5)return;
    for(i;i<=cs;++i)
    {
        d[i][1]=d[i-1][1]+d[i-2][1];
        d[i][2]=d[i-1][2]+d[i-2][2];
    }
}
int main()
{
    in(a),in(n),in(m),in(x);
    derive(n);int i,y1=0,a1=0;
//  for(i=1;i<=n;++i)printf("%d %d\n",d[i][1],d[i][2]);
    for(i=1;i<=n-1;++i)
    {
        a1+=d[i][1];
        y1+=d[i][2];
    }
    m-=a1*a;
    m/=y1;
    for(i=1;i<=x;++i)
    {
        people+=((d[i][1]*a)+(d[i][2]*m));
    }
    printf("%d",people);
    return 0;
}

本题解禁止抄袭！！！