P1057 传球游戏

Tag: dp $ \quad $ | Level: yellow

题目链接 | Here

题意

有$n$个人排成圆环传球,球从小李开始,每次只能向左,或者向右边传,总共能传$m$次,问有几种传法最终回到小李手中?

输入

$ 3 \leq n \leq 30 \ , \quad 1 \leq m \leq 30$

1
3 3	//n m

输出

1
2	//1->2->3->1 或 1->3->2->1

题解

首先考虑使用搜索,但是循环次数最多为$2^{30}$,所以抛弃,之后查询题解发现是使用$dp$或者打表实现。

$dp[i][j]$代表经过$i$次传球后传到$j$的方案数,因此可以轻易的发现,此时方案数由上一轮左边或者右边传球得来。

因此转移状态方程为:

只需对边界($1,n$)进行特殊处理便可。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
ll dp[35][35],n,m;

int main() {
std::ios::sync_with_stdio(false);
cin >> n >> m;
dp[0][1]=1;
for(int i=1; i<=m; i++) {
for(int j=1; j<=n; j++) {
if(j==1) dp[i][j]=dp[i-1][n]+dp[i-1][2];
else if(j==n) dp[i][j]=dp[i-1][1]+dp[i-1][j-1];
else dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];
}
}
cout << dp[m][1] << endl;
return 0;
}


--------------------------END--------------------------
喜欢的话,不妨请我喝杯奶茶(≧∇≦)ノ