P8725 题解

· · 题解

题目传送门

比较明显的 DP。

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

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

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

f_{i, j} = f_{i - 1, j} + f_{i - 1, j + 1}

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

计算时别忘了取模。


#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;
}