Oiclass P1263 题解

这真是一场愉快的传球游戏

再次是传统的五步

1. 划分阶段

这里我划分的状态是：每次传球完一种状态

2. 确定状态和状态变量

对于状态变量，我定义一个二维数组 \(f\) ，对于 \(f_{i,\ j}\) 他表示的是在 \(i\) 次传球后，\(j\) 手上的球的数量。

3. 确定决策和状态转移公式

对于这道题，决策的方式稍稍有那么一点点复杂，对于一种状态 （\(f_{i,\ j}\)）它有以下几种可能

• 当 \(j=1\) 也就是说是第一个人的时候，方程为：\(f_{i,\ j} = f_{i-1,\ n}+f_{i-1,\ 2}\)
• 当 \(j = n\) 也就是说是最后一个人的时候，方程为：\(f_{i,\ j}=f_{i-1\, j-1}+f_{i-1, 1}\)
• 在其余的情况，方程为：\(f_{i,\ j}=f_{i-1,\ j-1}+f_{i-1,\ j+1}\)

4. 确定边界

通过上面的分析和对题目不完全的理解，我们不难（很难）看出，边界条件就是: \[ f_{0,\ 1} = 1 \]

5. 实现

终于到了最简单的一步：实现，[欢呼]

OK，进入正题，实际上这道题的实现很简单，只需要这样几步就可以 AC：

• 输入（不输入算个啥？）
• 给边界条件赋值（不赋值就等s吧）
• 用状态转移公式计算每一个状态
• 输出

我相信你明白了？对吧？（反正我就这么看是没看明白）还有一个问题就是输出的时候究竟输出什么东西，我们可以把我们定义的二维数组 \(f\) 的内容写个表写来，发现 \(f_{m,\ 1}\) 就是我们想要的数，直接输出就 OK 了。

下面是我的代码，我为了方便，把数组 \(f\) 改成了我平时更常用的数组名 \(a\) ，见谅：

#include <iostream>

using namespace std;

int a[31][31], m, n;

int main() {
    cin >> n >> m;
    a[0][1] = 1;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (j == 1) {
                a[i][j] = a[i - 1][n] + a[i - 1][2];
            } else if (j == n) {
                a[i][j] = a[i - 1][1] + a[i - 1][n - 1];
            } else {
                a[i][j] = a[i - 1][j - 1] + a[i - 1][j + 1];
            }
        }
    }
    cout << a[m][1];
}