新手启示者
一次夏令营，小刚的老师带着同学们一起做一个传玩具的游戏。
游戏规则是这样的： n 个同学站成一个圆圈，其中的一个同学手里拿着一个玩具，当老师吹哨子时开始传玩具，每个同学可以把玩具传给自己左右的两个同学中的一个（左右任意），当老师再次吹哨子时，传玩具停止，此时，拿着玩具没有传出去的那个同学就是胜者，获得玩具拥有权。
聪明的小刚提出一个有趣的问题：有多少种不同的传递方法可以使得从小刚手里开始传的玩具，传了 m 次以后，又回到小刚手里。两种传玩具方法被视作不同的方法，当且仅当这两种方法中，接到玩具的同学按接玩具顺序组成的序列是不同的。比如有三个同学 1 号、 2 号、 3 号，并假设小刚为 1 号，玩具传了 3 次回到小刚手里的方式有 1 -> 2 -> 3 -> 1 和 1 -> 3 -> 2 -> 1 ，共 2 种。
输入描述 Input Description
一行，有两个用空格隔开的整数 n,m(3≤n≤30,1≤m≤30)
输出描述 Output Description
1 个整数，表示符合题意的方法数。
样例输入 Sample Input
3 3
样例输出 Sample Output
2
数据范围及提示 Data Size & Hint
40%的数据满足：3≤n≤30,1≤m≤20
100%的数据满足：3≤n≤30,1≤m≤30
解决者，重赏！0.01~1小时 悬赏20豆后采纳
1~24小时：悬赏10豆采纳
else 悬赏0豆
汪宇航在2021-04-27 20:29:08追加了内容
#include <bits/stdc++.h>
using namespace std;
int main(){
int a,b;
cin>>a>>b;
if(a>b)cout<<0;
else{
if(a%2==0&&b%2==1)cout<<0;
else{
if(a==b)cout<<2;
else{
//???
}
}
}
}
汪宇航在2021-04-29 19:45:25追加了内容
??????
汪宇航在2021-05-01 08:18:47追加了内容
............
中级启示者
好好的DP，被你弄成了什么鬼
状态转移方程
f[i][j]=f[i-1][j-1]+f[i-1][j+1];可以写出代码
for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
if(j==1)
f[i][j]=f[i-1][n]+f[i-1][2];//特判边界
else if(j==n)
f[i][j]=f[i-1][1]+f[i-1][n-1];
else
f[i][j]=f[i-1][j-1]+f[i-1][j+1];
}
}
注意边界情况
f[0][1]=1;新手启示者
悬赏！
新手启示者
@赵逸凡 @董宇昊
@陈曦 @李瑞曦
@曹博扬 @汪恺恒
@谭迪元 @赵睿泽
@张帆 @王泽宇
新手启示者
@酷町堂
新手启示者
hh
新手启示者
#include <bits/stdc++.h>
using namespace std;
long long f[1010][1010];
int main(){
int n,m;
cin>>m>>n;
f[0][1]=1;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
f[0][1]=1;
if(j==1)
f[i][j]=f[i-1][n]+f[i-1][2];
if(j==n)
f[i][j]=f[i-1][1]+f[i-1][n-1];
f[0][1]=1;
if(j!=1&&j!=n)
f[i][j]=f[i-1][j-1]+f[i-1][j+1];
}
}
cout<<f[m][n];
return 0;
}
@汪恺恒 ?
