题目大意
思路
考虑使用时空复杂度为 O ( t m ) O(tm) O(tm) 来解决这题。
设 d p i , j dp_{i, j} dpi,j 表示在第 i i i 秒体力为 j j j 时的方案数。
每次转移分为两种情况：
- 划桨： d p i − 1 , j + 1 dp_{i-1,j+1} dpi−1,j+1。
- 不划桨： d p i − 1 , j dp_{i-1,j} dpi−1,j。
于是转移方程为 d p i , j = d p i − 1 , j + 1 + d p i − 1 , j dp_{i,j}=dp_{i-1,j+1}+dp_{i-1,j} dpi,j=dpi−1,j+1+dpi−1,j。
然后判断一下是否还活着即可。
代码如下：
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
int d, t, m;
int dp[3007][1507]; //dp[i][j] 表示在第 i 秒体力为 j 的方案数
int main() {
cin >> d >> t >> m;
dp[0][m] = 1;
for(int i = 1; i <= t; i++)
for(int j = 0; j <= m; j++)
if(d - i + 2 * (m - j) > 0)
dp[i][j] = (dp[i - 1][j] + dp[i - 1][j + 1]) % mod;
cout << dp[t][0]; //题目说必须把 m 点体力花光，所以为 0
return 0;
}