题解 | #传球游戏#
传球游戏
https://ac.nowcoder.com/acm/problem/16619
- 题目考点：线性dp
- 题目大意：n个小牛♂牛围成一圈传球，问传球m次传回第一个人的情况有几种
- 题目分析：dp[ i ][ j ] 表示i次传球后，球在第j个人手里的情况，可以想到传球给这个人手里的是他左边的那个人（j-1）或者他右边那个人（j + 1 ）
因此dp[ i ][ j ] = dp [ i - 1 ][ j - 1 ] + dp [ i - 1] [ j + 1 ]
初始化dp[ 0 ] [ 1 ] = 1表示0次传球传给第一个人的情况只有一种
#include<iostream>
#include<algorith>
using namespace std;
int n, m, dp[35][35], la, ne;
int main()
{
dp[0][1] = 1;
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++){
la = j == 1 ? n : j-1; //当成一个圈处理
ne = j == n ? 1 : j+1;
dp[i][j] = dp[i-1][la]+dp[i-1][ne];
}
printf("%d", dp[m][1]);
return 0;
}
题解专栏 文章被收录于专栏
希望不断进步
，让我扣2办理