洛谷 1192:台阶问题(递推,DP)

摘要:
标题描述了有N个步骤。一开始,你可以走到底部的K个台阶,然后问有多少种不同的方法可以到达N个台阶。输入/输出样本输入样本#1:52输出样本#1:8显示,对于20%的数据,N≤ 10,千≤ 3.对于40%的数据,N≤ 1000; 对于100%数据,N≤ 100000,K≤ 100.每一次思路上升一步,它就必须上升一次,所以这取决于上一次台阶的位置。假设你一次走四步到50楼。通往第五十层的台阶数是方案49、48、47、46和45的总数。

题目描述

有 N 级的台阶,你一开始在底部,每次可以向上迈最多 K 级台阶(最少 1 级),问到达第 N 级台阶有多少种不同方式。

输入输出格式

输入格式:

两个正整数N,K。

输出格式:

一个正整数,为不同方式数,由于答案可能很大,你需要输出 ans mod 100003 后的结果。

输入输出样例

输入样例#1:

5 2

输出样例#1:

8

说明

对于 20% 的数据,有 N ≤ 10, K ≤ 3;

对于 40% 的数据,有 N ≤ 1000;

对于 100% 的数据,有 N ≤ 100000,K ≤ 100。

洛谷 1192:台阶问题(递推,DP)第1张

思路

每次上台阶时肯定都是一次走上去,那么就看上次所在台阶的位置。假如说一次上四个台阶,上到第50层。那么到第五十层的步数为在第49,48,47,46,45这些方案数相加。

写一个递推关系就好了:a[n]=a[n-1]+a[n-2]+……+a[n-k] 。对于到达每一层都是这样的方法,一直算下去就好了。注意要每次取模

AC代码

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <limits.h>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <string>
#define ll long long
#define ms(a) memset(a,0,sizeof(a))
#define pi acos(-1.0)
#define INF 0x3f3f3f3f
const double E=exp(1);
const int maxn=1e6+10;
const int mod=100003;
using namespace std;
int a[maxn];
int main(int argc, char const *argv[])
{
	ios::sync_with_stdio(false);
	int n,k;
	cin>>n>>k;
	ms(a);
	a[0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=k&&j<=i;j++)
			a[i]=(a[i]%mod+a[i-j]%mod)%mod;
	}
	cout<<a[n]%mod<<endl;	
	return 0;
}

免责声明:文章转载自《洛谷 1192:台阶问题(递推,DP)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇Tomcat *的安装和运行(绿色版和安装版都适用)MongoDB(4.4)使用下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

Qt5-控件-QRadioButton-单选按钮-用于从多个选项中选取一个-单选神器

#ifndef MAINWINDOW_H #define MAINWINDOW_H #include <QMainWindow> #include <QRadioButton> #include <QButtonGroup> class MainWindow : public QMainWindow { Q_...

【段错误 (核心已转储) 最高记录】

1 // Project name : 测试栈 2 // File name : main.cpp 3 // Author : iCoding 4 // E-mail : honi.linux@gmail.com 5 // Date & Time : Wed Aug 8 19:56:20 2012 6...

Qt编译mysql以及创建表后进行导入操作

       鉴于很多同学对Qt编译myql总是不能成功。出现各种问题,今天特此写出本教程,希望可以帮到须要的同学。        首先,须要明确编译的目的和原理。       目的:Qt 5.2版本号曾经都是不带mysql驱动的。所以须要进行编译mysql数据库驱动,仅仅有编译完毕后才干被Qt载入上。假设你安装的是Qt5.2以后版本号的,那就不须要了,...

linux系统编程:自己动手写一个who命令

who命令的作用用于显示当前有哪些用户登录到系统。 这个命令执行的原理是读取了系统上utmp文件中记录的所有登录信息,直接显示出来的 utmp文件在哪里呢? man who的时候,在手册下面有这么一段说明:意思就是不指定文件参数,那么读取的就是/var/run/utmp,到底是不是,验证下 If FILE is not specified, use /va...

纯前端版本号策略

近日在做的一个全静态项目,没有任何服务器逻辑,所以版本号策略也采用了纯前端的解决方案. 说实在话,其实都是被逼的,我只要修改一下服务器配置加简单的逻辑判断就可以了,但是后端工程师懒的搞,觉着巨复杂. 说到版本号,其实涉及到版本号有三个问题要考虑:版本发布问题 缓存和版本回滚问题 切换开发和维护环境的问题 其实方案很简单,类似于svn的版本策略,也就是如果有...

NX二次开发-获取面的法向向量UF_MODL_ask_face_data

1 NX9+VS2012 2 3 #include <uf.h> 4 #include <uf_modl.h> 5 #include <uf_obj.h> 6 #include <uf_ui.h> 7 8 9 UF_initialize()...