P1192 台阶问题

admin

题目描述
有 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 。

倚窗倾听风吹雨

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. }

复制代码

黄煦喆

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. }
    

复制代码

admin

可以再优化一下

小猪快跑jpg

#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);
}
//-------用递归做老是出错，就放弃了------------//

GTR

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. }

复制代码