洛谷P1057 传球游戏【dp】

题目：https://www.luogu.org/problemnew/show/P1057

题意：

n个人围成一个圈，传球只能传给左边或是右边。

从第一个人开始传起，经过m次之后回到第一个人的传球方案有多少种。

思路：

发现有的时候dp的转移方程可以通过写递归得到。把递归给变成dp

用$dp[i][j]$表示第$j$号开始传$i$次回到$j$的方案数。很容易想到，第$i$次回到$j$时，一定是$j-1$或是$j+1$传回来的。

所以可以得到$dp[i][j] = dp[i-1][j-1]+dp[i-1][j+1]$

初始时是$dp[0][0] = 1$,终态是$dp[m][0]$

要注意因为是一个圈，所以我们用%来处理。为避免负数，$-1$的时候要$+n$

 #include<stdio.h>

 #include<stdlib.h>

 #include<map>

 #include<set>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<cmath>

 #include<queue>

 #define inf 0x7f7f7f7f

 using namespace std;

 typedef long long LL;

 typedef pair<int, int> pr;

 int n, m;

 int dp[][];

 //dp[i][j]表示传i次回到j的方案数

 //dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 

 //int dfs(int x, int id)

 //{

 //    if(dp[x][id])return dp[x][id];

 //    if(x == 0){

 //        return 1;

 //    }

 //    int ans = 0;

 //    ans += dfs(x - 1, (id + 1) % n);

 //    ans += dfs(x - 1, (id - 1) % n);

 //    dp[x][id] = ans;

 //    return ans;

 //}

 int main()

 {

     scanf("%d%d", &n, &m);

     dp[][] = ;

     for(int i = ; i <= m; i++){

         for(int j = ; j < n; j++){

             dp[i][j] = dp[i - ][(j -  + n) % n] + dp[i - ][(j + ) % n];

         }

     }

     printf("%d\n", dp[m][]);

     return ;

 }

巴特西

洛谷P1057 传球游戏【dp】

最新文章

热门文章