算法1

(线性DP) $O(n*m)$

一开始我想的是f[][]表示第i秒离峡谷的距离j,但是发现题目必须要把体力用完,瞄了一眼别人的题解发现都是用时间和体力做状态的.瞬间觉得自己还是太 弱 了！

f[][]表示第i秒用了j点体力的方案.此处迷惑点就在如何判断此时是否跌落峡谷.这里我们可以手动算一下.
因为在i秒种用了j点体力,所以向上划了j米,则向下滑了i-j米,如果要保证不滑下峡谷则下滑的距离必须小于初始离峡谷的距离+上滑的距离，即i-j<j+d=>i<2*j+d.

状态转移方程:

f[i][j]=(f[i][j]+f[i-1][j-1])%mod;//划了
if(i>=j&&2*j+d>i) f[i][j]=(f[i][j]+f[i-1][j])%mod;//没划

这个样例比较特别:由于只要有体力则可以在任意时刻划船,但是如果离谷底近的话就不能不划船。
这里样例中d=1所以如果不划的话就会跌落谷底,所以此时不划船是非法状态！

时间复杂度

O(n*m)

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N=3e3+10;

int d,n,m;
ll f[N][N],mod=1000000007;


int main()
{
    memset(f,0,sizeof f);
    cin>>d>>n>>m;

    if(d>1) f[1][0]=1;//如果一开始就位于临界点则这时候不划船就是非法方案了，样例就是这种情况！
    f[1][1]=1;
    for(int i=1;i<=n;i++)
    for(int j=0;j<=m;j++)
    {
    f[i][j]=(f[i][j]+f[i-1][j-1])%mod;
    if(i>=j&&2*j+d>i) f[i][j]=(f[i][j]+f[i-1][j])%mod;
    }

    cout<<f[n][m];
    return 0;
}