侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 655 篇文章
  • 累计创建 127 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2023-01-11 / 0 评论 / 0 点赞 / 37 阅读 / 648 字
温馨提示:
本文最后更新于 2023-01-11,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

画中漂流 - 蓝桥云课


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

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

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

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

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

输入格式

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

输出格式

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

样例输入

1 6 3

样例输出

5

评测用例规模与约定

对于 50%50 \% 的评测用例,1T3501 \leq T \leq 350

对于所有评测用例,1T3000,1DT,1M15001 \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));
    }
}
0

评论区