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

题目描述

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

输入输出格式

输入格式：

输入文件的仅包含两个正整数N，K。

输出格式：

输入文件stair.out仅包括1个正整数，为不同方式数，由于答案可能很大，你需要输出mod 100003后的结果。

输入输出样例

输入样例#1：

5 2

输出样例#1：

说明

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

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

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

代码

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

int n,k;

int f[];

int main(){

    scanf("%d%d",&n,&k);

    f[]=;

    for(int j=;j<=n;j++){

        for(int i=;i<=k;i++){

            f[j]=(f[j]+f[j-i])%;

        }//这里少了一句话，j应该大于或等于i

    }

    printf("%d\n",f[n]);

    return ;

}

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int n,k,f[];

 int main(){

     scanf("%d%d",&n,&k);

     f[]=;

     for(int i=;i<=k;i++){

         for(int j=i;j<=n;j++){

             f[j]=(f[j]+f[j-i])%;

         }

         for(int ll=;ll<=n;ll++){

             printf("%d ",f[ll]);

         }puts("");

     }

     printf("%d\n",f[n]);

     return ;

 }

不满足后效性的错误代码

看题解说是斐波那契数列变形,dp也可以啊

感觉和TYVJ 1015是差不多的

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<algorithm>

#define inf 1000000000

using namespace std;

int n;

int m[],f[];

int main()

{

    memset(f,,sizeof(f));

    f[]=;

    for(int i=;i<=;i++)

        scanf("%d",&m[i]);

    scanf("%d",&n);

    for(int i=;i<=;i++)

        for(int j=;j<=n;j++)

            if(f[j]<inf)

                f[j+i]=min(f[j+i],f[j]+m[i]);

    printf("%d\n",f[n]);

    return ;

}

Fi表示移动i公里的最小代价Fi表示移动i公里的最小代价

则Fi=min{fi−j+mj}

巴特西

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

题目描述

输入输出格式

输入输出样例

说明

代码

最新文章

热门文章