洛谷P1057 [NOIP2008 普及组] 传球游戏
#include<iostream> using namespace std; int n;// n个人传球游戏 默认开始球在编号为1的位置 int m;// 传递m次球 int main(){ cin>>n>>m; // 动态转方程： // 球传递到编号为k人的手中 // 种类总数 = 传递到k-1编号种类总数 + 传递到k+1编号种类总数 // 考虑界限：当传递次数为0次除了1为一种其他的为0 /* 0 1 2 3 |----------------| 0 | 0 | 1 | 0 | 0 | ------------------ 1 | 0 | 0 | 1 | 1 | ------------------ 2 | 0 | 2 | 1 | 1 | ------------------ 3 | 0 | 2 | 3 | 3 | */ int DP[31][31] = {}; DP[0][1] = 1; // 传球次数 for(int C=1;C<=m;C++){ for(int N=1;N<=n;N++){// 学生的编号 // 因为构成一个圈当编号为1的时候 == 编号为n以及2的和 if(N==1){ DP[C][1] = DP[C-1][n] + DP[C-1][2]; }else if(N==n){// 编号为n也是个扣环特殊点 DP[C][n] = DP[C-1][n-1] + DP[C-1][1]; }else{ DP[C][N] = DP[C-1][N-1] + DP[C-1][N+1]; } } } cout<<DP[m][1]; return 0; }
原文地址：https://blog.csdn.net/Gjanuary/article/details/137964670
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！