洛谷 P8725 [蓝桥杯2020省AB3] 画中漂流：
- [1]读题：
在梦境中，你踏上了一只木䇝，在江上漂流。
根据对当地的了解，你知道在你下游 D 米处有一个峡谷，如果你向下游前进大于等于 D 米则必死无疑。
现在你打响了急救电话，T 秒后救援队会到达并将你救上岸。水流速度是 1 m/s，你现在有 M 点体力。每消耗一点体力，你可以划一秒桨使船向上游前进 1 m，否则会向下游前进 1 m (水流)。M 点体力需在救援队赶来前花光。因为江面太宽了，凭借你自己的力量不可能上岸。
请问，有多少种划桨的方案可以让你得救。
两个划桨方案不同是指：存在某一秒钟，一个方案划桨，另一个方案不划。
输入格式
输入一行包含三个整数 D，T，M。
输出格
输出一个整数，表示可以让你得救的总方案数，答案可能很大，请输出方案数除以1000000007即 10^9+7的余数。
样例输入
1 6 3
样例输出
5
- [2] 理解题意：
qwq，很明显，这是一道动态规划dp的题，我们就用一个f[i][j]来存储方案数，其中用i来表示时间，用j来表示体力。
那么于是我们枚举时间和体力转移。我们通过时间和体力算出距离，用了多少体力就向上游了多少。设原始距离为 d 当前时间为 i 当前消耗的体力 j，则向上游长度为 j ，向下漂流长度为 i+j，当前位置为 d+2*j-i。
因为同一时间有游于不游两种方案数，所以我们推出我们的究极无敌状态转移方程：
f[i][j]=f[i-1][j]+f[i-1][j-1]
另外，还要对结果取模哟 qwq。
代码如下：
#include <bits/stdc++.h> using namespace std; int mod = 1e9 + 7; int f[3030][3030]; int d, t, m; int main(){ scanf("%d%d%d",&d,&t,&m); f[0][m] = 1; for (int i = 1; i <= t; ++i) { for (int j = 0; j <= m; ++j) { if (d + (m - j) - (i - (m - j))> 0) { f[i][j] = (f[i - 1][j] + f[i - 1][j + 1]) % mod; } } } printf("%d",f[t][0]); return 0; }
欧克，华丽地结束！！！
——————————————————————————华丽的分割线qwq