【ybt高效进阶1-1-4】【luogu P1057】传球游戏
传球游戏
题目链接:ybt高效进阶1-1-4 / luogu P1057
题目大意
就是一个长度是 n 的环,走 m 步走回原来的位置的方案有多少种。
思路
我们设 f i , j f_{i,j} fi,j 为从 1 1 1 号点出发,走了 i i i 步,现在走到 j j j 点的方案数。
那么初始化就是 f 0 , 1 = 1 f_{0,1}=1 f0,1=1。(一开始待在 1 1 1 号点)
那只能从两边走过来,那就是
f
i
,
j
=
f
i
−
1
,
j
+
1
+
f
i
−
1
,
j
−
1
f_{i,j}=f_{i-1,j+1}+f_{i-1,j-1}
fi,j=fi−1,j+1+fi−1,j−1。
但是这个图是一个环,就要判断一下,如果第二维超了
1
∼
n
1\sim n
1∼n 的范围就要让值变一下,
0
0
0 变成
n
n
n,
n
+
1
n+1
n+1 变成
1
1
1。
最后输出 f m , 1 f_{m,1} fm,1 即可。
代码
#include<cstdio>
using namespace std;
int n, m, f[31][31];
int ch(int x) {
if (x == 0) return n;
if (x == n + 1) return 1;
return x;
}
int main() {
scanf("%d %d", &n, &m);
f[0][1] = 1;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
f[i][j] = f[i - 1][ch(j + 1)] + f[i - 1][ch(j - 1)];
printf("%d", f[m][1]);
return 0;
}
相关文章
- 游戏开发常遇到数据一致性BUG,怎么解?
- html5游戏开发--"动静"结合(二)-用地图块拼成大地图 & 初探lufylegend
- 【wikioi】1108 方块游戏(模拟)
- archdexls主题游戏页面game-play.php有评论时,报错( ! ) Warning: printf(): Too few arguments in D:wampwwwwp-contentthemesarcadexlsgames-play.php on line 97
- 【2019CSPJ普及组】T1:数字游戏 试题解析
- 【2010NOIP普及组】T4. 三国游戏 试题解析
- 20个免费的 JavaScript 游戏引擎分享给开发者
- 报数游戏。
- 网页游戏分线到不分线
- 基于HTML5坦克大战游戏简化版
- 【ybt高效进阶4-1-3】【luogu P5462】龙珠游戏 / X龙珠