♐ CSP_J 组真题
2008年
3. 传球游戏

线上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号手里的方案总数。由于球可以从前后两个方向传来,所以 dp[i][j]=dp[i1][j1]+dp[i+1][j1]dp[i][j] = dp[i-1][j-1]+dp[i+1][j-1]。即:第 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;
}