线上OJ:
一本通:1944【08NOIP普及组】传球游戏 (opens in a new tab)
AcWing:435.传球游戏 (opens in a new tab)
洛谷:P1057 [NOIP2008 普及组] 传球游戏 (opens in a new tab)
核心思想:
解法一、这类题可采用动态规划的思想。
令 dp[i][j] 表示(从1号开始)经过 j 次传球后,球在i号手里的方案总数。由于球可以从前后两个方向传来,所以 。即:第 i 个点 j 次的方案总数等于前后两个点 j-1 次的方案数总和。
解法一、动态规划DP
#include <bits/stdc++.h>
using namespace std;
const int N = 35;
int n, m, dp[N][N]; // dp[i][j]表示(从1号开始)经过 j 次传球后,球在i号手里的方案总数 dp[i][j] = dp[i-1][j-1]+dp[i+1][j-1]
int main()
{
scanf("%d %d", &n, &m);
memset(dp, 0, sizeof(dp));
dp[1][0] = 1; // 从1号开始,经过0次传球后,球在1号手里的方案总数。只有1种,就是不传
for(int j = 1; j <= m; j++)
for(int i = 1; i <= n; i++)
{
int pre, nxt;
// 处理前后两个点的坐标边界
i == 1 ? pre = n : pre = i-1;
i == n ? nxt = 1 : nxt = i+1;
dp[i][j] = dp[pre][j-1] + dp[nxt][j-1]; // 核心语句第i个点j次的方案总数等于前后两个点j-1次的方案数总和
}
printf("%d\n", dp[1][m]);
return 0;
}