axuhongbo的个人博客

http://bailian.openjudge.cn/xly2019/D/
描述
小S在玩一个叫上楼梯的游戏。楼梯一共有n层台阶。
因为腿长的限制，小S每次最多只能上k层台阶。
小S是一个迷信的人，所以他不希望自己某一步走的步数的数字里有"4"，（比如4，14，44都含有数字"4"）。
现在，小S想要知道，有多少种走完这n层台阶的方案？
输入
输入包含多组数据。

每组数据第一行输入一个整数 n, k(1 <= k <= n <= 50)。

输入以 n,k=0 结束。
输出
对于每组数据，输出一行一个整数，表示答案。
样例输入
10 1
10 2
18 8
0 0
样例输出
1
89
71262
提示
注意答案可能超过 int 所能表示的范围，请谨慎选择存储答案以及中间数据的数据类型。
#include <iostream>
#include <cstring>
#include <string>
#include <bits/stdc++.h>
using namespace std;
const int maxn = 60;
typedef long long ll;
ll dp[maxn];
ll search(int n, int k)
{
    if (dp[n] > 0)
    {
        return dp[n];
    }
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j <= min(i, k); j++)
        {
            string str ;
            stringstream ss;
            ss<<j;
            ss>>str;
            if (str.find("4") == string::npos)
            {
                dp[i] += dp[i - j];
            }
        }
    }
    return dp[n];
}

int main()
{
    int n, k;
    while (cin >> n >> k)
    {
        if (n == 0 && k == 0)
        {
            break;
        }
        memset(dp, 0, sizeof(dp));
        cout << search(n, k) << endl;
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <string>
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define maxn 60
ll dp[maxn];

int main()
{
    int n,k;
    while(cin>>n>>k)
    {
       // cin>>n>>k;
        memset(dp,0,sizeof dp);
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2; i<=n; i++)
        {
            for(int j=1; j<=min(i,k); j++)
            {
                string str;
                stringstream ss;
                ss<<j;
                ss>>str;

                if(str.find("4")==string::npos){
                    dp[i]+=dp[i-j];
                }

            }
        }
        cout<<dp[n]<<endl;

    }

    return 0;
}