自动搬运

查看原文

来自洛谷，原作者为

	FutureSnow OI Track Complete

搬运于2025-08-24 22:41:50，当前版本为作者最后更新于2023-02-23 19:42:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

比较明显的 DP。

设 $f_{i, j}$，表示时间为 $i$，体力为 $j$ 的方案数。

于是我们枚举时间和体力转移。我们通过时间和体力算出距离，用了多少体力就向上游了多少。设原始距离为 $d$ 当前时间为 $i$ 当前剩余体力 $j$， 则向上游长度为 $m - j$，向下漂流长度为 $i - (m - j)$，当前位置为 $d + (m - j) - (i - (m - j))$。

如果当前状态所在位置 $> 0$，则可以转移。不难推出

两种决策分别表示不用体力和用体力。

计算时别忘了取模。

#include <bits/stdc++.h> 

using namespace std;

const int mod = 1e9 + 7;
int f[3030][3030];
int d, t, m;
int main(){
    cin >> d >> t >> m;
    f[0][m] = 1;
    for (int i = 1; i <= t; ++i) {
        for (int j = 0; j <= m; ++j) {
            int len = d + (m - j) - (i - (m - j));
            if (len > 0) {
                f[i][j] = (f[i - 1][j] + f[i - 1][j + 1]) % mod;
            }
        }
    }
    cout << f[t][0] << endl;
    return 0;
}