点我进入题目
题目大意：n个小孩围一圈传球，每个人可以给左边的人或右边的人传球，1号小孩开始，一共传m次，请问有多少种可能的路径使球回到1号小孩。
输入输出：输入n，m，输出路径的数量。
数据范围：40% 3<=n<=30 1<=m<=20 100% 3<=n<=30 1<=m<=30
我是这么想的：膜拟过程，从1号小孩开始dfs，然后加一个记忆化搜索节省时间。
dfs(num,tim)表示球传到第num个小孩，已经传过tim次时候，d[num][tim]表示球传到第num个小孩，已经传过tim次时候已经记录过的可能传到1号小孩的次数。
刚开始的时候默认1号小孩只把球传给2号小孩，因为传给n号小孩和传给2号小孩的情况是对称的，所以乘以2，理论上节省一半时间(实际上由于记忆化搜索，节省不了多少时间)
代码如下：
/*
P1057 传球游戏
*/
#include
#include
using namespace std;
int n,m;
int d[31][31];
int search(int num,int tim)
{if(tim==m){if(num==1)return 1;else return 0;}else if(d[num][tim]!=-1)return d[num][tim];else return d[num][tim]=search(num==n?1:num+1,tim+1)+search(num==1?n:num-1,tim+1);
}
int main()
{memset(d,-1,sizeof(d));cin >> n >> m;cout << search(2,1)*2 << endl;return 0;
}