关于P1255的解法

Novaorbit · 2020-12-04 09:42:05 · 个人记录

其实数楼梯问题也就是个递推问题。

简单分析一下：对于长度为n的楼梯，对于第一步（暂且不考虑之后的选择），有以下两种选择：走一级或走两级。显而易见，第一步的选择对于之后的决策并没有实质性的影响。也就是说，如果把n级楼梯问题的关系式写作f(n)，则可以得出等式：

由此便可以推出此题解法。

另：不要用递归！会TLE！（其实偶尔用一用也不错）

代码如下：

#include<bits/stdc++.h>
using namespace std;
short n,road[5010][2000],poi=1,len[5010];//尽量节省空间 

//long long st(long long a)
//{ 
//  if(a>=2)
//      return st(a-1)+st(a-2);
//  if(a==1)
//      return st(a-1);
//  if(a==0)
//      return 1;
//}
//以上是递归式。结果40分。原因：TLE  

short mx(short a,short b)
{
    if(a>=b)
        return a;
    return b;
}

void jf(int n)//是的！没想到吧！这题要用高精！ 
{
    short a=n-1,b=n-2,i=0;//懒得打n-1,n-2了 
    for(poi=0;poi<mx(len[a],len[b]);poi++)
    {
        road[n][poi]=road[a][poi]+road[b][poi];
        len[n]++;
    }
    while(i<poi)
        if(road[n][i++]>=10)
        {
            road[n][i-1]-=10;
            road[n][i]++;
        }
    if(road[n][len[n]])
        len[n]++;
}//不用高精的话。50分走好。 

int main()
{
//  freopen("P1255.in","r",stdin);
//  freopen("P1255.out","w",stdout);
    cin>>n;
    road[1][0]=1;road[2][0]=2;len[0]=1;len[1]=1;
    for(int i=3;i<=n;i++)
        jf(i);
    if(road[n][poi]==0)
        poi--;
    for(int i=poi;i>=0;i--)
        cout<<road[n][i];
    return 0;
}