洛谷Oj-台阶问题————DP

小灰灰 2022-05-18 05:20 120阅读 0赞

1479: 台阶问题  
时间限制: 1 Sec 内存限制: 128 MB

提交: 262 解决: 77 统计  
**题目描述**  
有 N 级的台阶，你一开始在底部，每次可以向上迈最多 K 级台阶（最少 1 级），问到达第 N 级台阶有多少种不同方式。  
**输入**  
多组输入,两个正整数N(N ≤ 1000)，K(K ≤ 100)。  
**输出**  
一个正整数，为不同方式数，由于答案可能很大，你需要输出 ans mod 100003 后的结果。  
**样例输入**  
5 2  
**样例输出**  
8  
**来源**  
丁金峰

--------------------

推这个规律写了好几张纸

dp\[n\]=\{ 2n−1%mod∑ki=1dp\[n−i\]%modn≤kn>k  d p \[ n \] = \{ 2 n − 1 % m o d n ≤ k ∑ i = 1 k d p \[ n − i \] % m o d n > k

--------------------

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN=1005;
    const int c=100003;
    int a[MAXN];
    int main()
    {
        int n,k;
        while(~scanf("%d %d",&n,&k))
        {
            if(k==1)    
            {
                printf("1\n");
                continue;
            }
            memset(a,0,sizeof(a));
            a[1]=1;a[2]=2;
            for(int i=3;i<=k;i++)
                a[i]=(a[i-1]%c+(2*a[i-2])%c)%c;
            for(int i=k+1;i<=n;i++)
                for(int j=1;j<=k;j++)
                    a[i]=(a[i]%c+a[i-j]%c)%c;
    
            printf("%d\n",a[n]%c);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，120人围观）

还没有评论，来说两句吧...

相关阅读

相关 DP练习-初阶题（洛谷）

DP练习-初阶题（洛谷）前言： DP对我来说，一直都是比较令我头大的，现在的水平都是处于入门级的水平，这一周基本上主要就是强化DP 虽然关于DP的博客写过一点题

忘是亡心i/ 2023年06月30日 02:51/ 0 赞/ 96 阅读

相关洛谷

题目描述有一次，小鱼要从A处沿直线往右边游，小鱼第一秒可以游7米，从第二秒开始每秒游的距离只有前一秒的98%。有个极其邪恶的猎人在距离A处右边s米的地方，安装了一个隐蔽

「爱情、让人受尽委屈。」/ 2022年05月31日 02:10/ 0 赞/ 189 阅读

相关洛谷P1192 台阶问题

题目描述有N级的台阶，你一开始在底部，每次可以向上迈最多K级台阶（最少1级），问到达第N级台阶有多少种不同方式。输入输出格式输入格式：输入文件的仅

缺乏、安全感/ 2022年05月29日 00:45/ 0 赞/ 127 阅读

相关洛谷P1052 过河+状压dp

题目描述在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把

布满荆棘的人生/ 2022年05月26日 01:52/ 0 赞/ 116 阅读

相关洛谷Oj-台阶问题————DP

1479: 台阶问题时间限制: 1 Sec 内存限制: 128 MB 提交: 262 解决: 77 统计题目描述有 N 级的台阶，你一开始在底部，每次可以向

小灰灰/ 2022年05月18日 05:20/ 0 赞/ 121 阅读

相关洛谷OJ P1087 FBI树

题目：题目描述我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。 FBI树是一种二叉树

一时失言乱红尘/ 2022年04月14日 06:57/ 0 赞/ 298 阅读

相关【洛谷4719】动态dp（树链剖分，dp，矩阵乘法）

前言其实我只是为了过掉模板而写的ddp，实际应用被吊着锤 Solution 并不想写详细的过程一句话过程：将子树中轻儿子的贡献挂到这个点上面来详细版：（

淡淡的烟草味﹌/ 2022年01月09日 07:21/ 0 赞/ 166 阅读

相关 TYVJ P1015 公路乘车 &&洛谷 P1192 台阶问题 Label:dp

题目描述有N级的台阶，你一开始在底部，每次可以向上迈最多K级台阶（最少1级），问到达第N级台阶有多少种不同方式。输入输出格式输入格式：输入文件的仅包含两

- 日理万妓/ 2022年01月09日 07:03/ 0 赞/ 148 阅读

相关洛谷P1220 关路灯【区间dp】

题目：[https://www.luogu.org/problemnew/show/P1220][https_www.luogu.org_problemnew_show_P12

我就是我/ 2021年12月12日 15:43/ 0 赞/ 198 阅读

相关洛谷P1280 尼克的任务【线性dp】

题目：[https://www.luogu.org/problemnew/show/P1280][https_www.luogu.org_problemnew_show_P12

古城微笑少年丶/ 2021年09月29日 12:16/ 0 赞/ 241 阅读