题目描述

上体育课时，墨老师经常带着同学们一起做游戏。这次，墨老师带着同学们一起做传球游戏，游戏规则是这样的：N个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师再次吹哨子时，传球停止，此时拿着球没传出去的那个同学就是败者，要给大家表演一个节目。

聪明的张琪曼提出一个有趣的问题：有多少种不同的传球方法可以使得从张琪曼手里开始传的球，传了Ｍ次以后，又回到张琪曼手里。两种传球的方法被称作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。比如有3个同学1号、2号、3号，并假设张琪曼为1号，球传了3次回到张琪曼手里的方式有1à2à3à1和1à3à2à1，共两种。

 

输入

有两个用空格隔开的整数N，M（3≤N≤30，1≤M≤30）。

 

输出

有一个整数，表示符合题目的方法数。

 

样例输入

复制样例数据

3 3

样例输出

2 解题思路：dp[i][j]表示第i次传到第j个人的方案数，由左右两个人传i-1次得到

#include
     
      #define REP(i, a, b) for(int i = (a); i <= (b); ++ i)#define REP(j, a, b) for(int j = (a); j <= (b); ++ j)#define PER(i, a, b) for(int i = (a); i >= (b); -- i)using namespace std;const int maxn = 45;int dp[maxn][maxn];template 
      
       inline void rd(T &ret) {    char c;    ret = 0;    while ((c = getchar()) < '0' || c > '9');    while (c >= '0' && c <= '9') {        ret = ret * 10 + (c - '0'), c = getchar();    }}int main() {    int tot, cnt;    rd(tot);    rd(cnt);    dp[0][1] = 1;    for (int i = 1; i <= cnt; i++) {        for (int k = 1; k <= tot; k++) {            if (k == 1)dp[i][k] = dp[i - 1][tot] + dp[i - 1][2];            else if (k == tot)dp[i][k] = dp[i - 1][1] + dp[i - 1][tot - 1];            else dp[i][k] = dp[i - 1][k+1] + dp[i - 1][k - 1];        }    }    cout << dp[cnt][1] << endl;}