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

小灰灰 2022-05-18 05:20 199阅读 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 条评论，199人围观）

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

相关阅读

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

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

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

相关【洛谷P4719】动态dp

Description 给定一棵树，点带点权，允许修改点权，求每次修改之后树的最大独立集 Solution ddp用LCT维护前置知识（静态树的最大独立集问

柔光的暖阳◎/ 2023年06月05日 08:53/ 0 赞/ 32 阅读

相关洛谷状压DP做题记录

P2915 \[USACO08NOV\]奶牛混合起来Mixed Up [题面][Link 1] 确实是状压的入门题用dp\[i\]\[j\] 表示以i结尾，状态为j时

拼搏现实的明天。/ 2023年06月04日 07:59/ 0 赞/ 18 阅读

相关洛谷

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

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

相关洛谷P1192 台阶问题

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

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

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

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

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

相关洛谷OJ P1087 FBI树

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

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

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

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

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

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

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

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

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

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

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