【记忆化搜索】画中漂流【蓝桥杯】

题目

画中漂流 - 蓝桥云课

---

在梦境中，你踏上了一只木筏, 在江上漂流。

根据对当地的了解，你知道在你下游 $D$ 米处有一个峡谷，如果你向下游前进大于等于 $D$ 米则必死无疑。

现在你打响了急救电话， $T$ 秒后救援会到达并把你救上岸。水流速度是 $1 \sim m$, 你现在有 $M$ 点体力。每消耗一点体力，你可以划一秒桨使船向上游前进 $1 \sim m$，否则会向下游前进 $1 \sim m$ (水流)。 $M$ 点体力需在救援队赴来前花光。因为江面太宽了，凭借你自己的力量不可能上岸。

请问, 有多少种划桨的方案可以让你得救。

两个划桨方案不同是指; 存在某一秒钟, 一个方案划桨, 另一个方案不划。

输入格式

输入一行包含三个整数 $D, T, M$。

输出格式

输出一个整数, 表示可以让你得救的总方案数, 答案可能很大, 请输出方案数除以 $1,000,000,007$ 的余数。

样例输入

1 6 3

样例输出

5

评测用例规模与约定

对于 $50 \%$ 的评测用例，$1 \leq T \leq 350$。

对于所有评测用例，$1 \leq T \leq 3000,1 \leq D \leq T, 1 \leq M \leq 1500$。

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

解题

方法一：记忆化搜索

思路

直接递归肯定会 TLE，好在状态可以复用，遂使用记忆化搜索。

代码

import java.util.*;
import java.io.*;

public class P2358 {
    static final int T = 3010, M = 1510, MOD = (int) 1e9 + 7;
    static int d, t, m;
    static int[][] memos = new int[T][M];
    static {
        for (int[] arr : memos) Arrays.fill(arr, -1);
    }

    static int dfs(int d, int t, int m) {
        if (memos[t][m] != -1) return memos[t][m];
        if (t == 0) {
            if (m != 0) return 0;
            return memos[0][0] = 1;
        }
        memos[t][m] = 0;
        if (m > 0) memos[t][m] = (memos[t][m] + dfs(d + 1, t - 1, m - 1)) % MOD;
        if (d > 1) memos[t][m] = (memos[t][m] + dfs(d - 1, t - 1, m)) % MOD;
        return memos[t][m];
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int d = (int) in.nval;
        in.nextToken();
        int t = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        System.out.println(dfs(d, t, m));
    }
}