华师一附中OI组

标题: P1192 台阶问题 [打印本页]
作者: admin    时间: 2018-6-8 10:44
标题: P1192 台阶问题
题目描述
有 NN 级的台阶，你一开始在底部，每次可以向上迈最多 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 。
作者: GTR    时间: 2018-6-13 22:17
  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. int main()
  5. {
  6.     int s[100002]= {0},n,k;
  7.     scanf("%d%d",&n,&k);
  8.     s[0]=1;
  9.     for(int i=1; i<=n; i++)
  10.     {
  11.         for(int j=1; j<=k && (i-j)>=0; j++)
  12.             s[i]+=s[i-j];
  13.         s[i]=s[i]%100003;
  14.     }
  15.         printf("%d",s[n]);
  16.         return 0;
  17. }
复制代码
作者: 小猪快跑jpg    时间: 2018-9-5 19:55
#include<bits/stdc++.h>
using namespace std;
int n,k,jt[100001];
int main()
{
        jt[0]=1;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        {
        for(int j=1;j<=k;j++)
                {
            jt[i]+=jt[i-j];
            if(i<=j) break;
            else;
        }
        jt[i]%=100003;
    }
    cout<<jt[n];
    exit(0);
}
//-------用递归做老是出错，就放弃了------------//
作者: admin    时间: 2018-9-6 16:16
可以再优化一下
作者: 黄煦喆    时间: 2018-9-9 21:26
  1. #include<iostream>
  2. using namespace std;
  3. long long f[100001]={1},k,n;
  4. long long s=1;
  5. int main()
  6. {
  7.     cin>>n>>k;
  8.     for(int i=1;i<=n;i++)
  9.     {
  10.         f[i]=s;
  11.         if(i>=k)s=(s*2-f[i-k]+100003)%100003;
  12.         else s=(s<<1)%100003;
  13.     }
  14.     cout<<f[n];
  15.     return 0;
  16. }
复制代码
作者: 倚窗倾听风吹雨    时间: 2018-9-11 17:03
本帖最后由 倚窗倾听风吹雨 于 2018-9-11 17:05 编辑

emmmm,递归解法。
  1. #include<iostream>
  2. using namespace std;
  3. int n,k,ans,f[100010];
  4. int dg(int x)
  5. {
  6.     int a=0;
  7.     if(f[x]!=0)return f[x];
  8.     for(int i=1;i<=k;i++)
  9.         if(x-i>=0)a=(a+dg(x-i))%100003;
  10.     f[x]=a;
  11.     return a;
  12. }
  13. int main()
  14. {
  15.     cin>>n>>k;
  16.     f[0]=1;f[1]=1;
  17.     cout<<dg(n)%100003;
  18. }
复制代码






欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2