粥可赛艇——重庆大学月赛

传说粥老板很喜欢锻炼身体，也很喜欢赛艇。

但他在赛艇的时候总是控制不好赛艇的方向，每划一下都会跑到别的赛道上。

假设粥老板正在一条直线赛道，从左往右依次是1号赛道，2号赛道，3号赛道……如此类推，

为了让粥老板更自由，总共有无限条赛道！粥老板需要划2*n下才能到达终点，但是正如上面所说，粥老板每划一下都会偏离原来的赛道，也就是会蹿到相邻的赛道，当然粥老板是不会划到1号赛道的左边去。粥老板一定是从1号赛道开始划的，同样，最后必须回到1号赛道到达终点。已知粥老板在这过程之中，一共调整了2*k-1次方向，那么请问粥老板一共有多少种方案来划完这2*n步呢？

（两种方案视为不同当且仅当两种方案的某一步所在的赛道不同）

粥可赛艇！
Input

第一行为一个整数T，表示有T组数据（T≤100）

接下来的T行的之内每行包含两个整数n,k（1≤k≤n≤20）
Output

每行输出一个数，即是方案数
Sample Input

2
2 1
4 2

Sample Output

1
6

Hint

对于第一组样例粥老板的方案为1-2-3-2-1



对于第二组样例，粥老板的方案为:



1-2-3-2-3-4-3-2-1；1-2-3-4-3-4-3-2-1；



1-2-3-4-3-2-3-2-1；1-2-1-2-3-4-3-2-1；

1-2-3-2-1-2-3-2-1；1-2-3-4-3-2-1-2-1；

题解：本题也是dp，状态方程是：

1.k是奇数时，有可能此时必须向左划，此时应该是上一次在右边来的，可能变轨，也可能没有。

dp[i][j][k] = dp[i-1][j+1][k-1]+dp[i-1][j+1][k];

dp[i][j][k] = dp[i-1][j-1][k-1]+dp[i-1][j-1][k];

#include 
#include 
#include using namespace std;int t;
int n,k;
int dp[45][45][45];//表示第i次划行，到了第j个航道，已经变了k次轨int main()
{memset(dp,0,sizeof(dp));//for(int i=0;i<=n;i++)//dp[i][i][0] = 1;for(int i=0;i<45;i++)dp[i][i+1][0] = 1;for(int i=1;i<45;i++){for(int j=1;j<45;j++){for(int k=1;k<45;k++){if(k&1)dp[i][j][k] = dp[i-1][j+1][k-1]+dp[i-1][j+1][k];elsedp[i][j][k] = dp[i-1][j-1][k-1]+dp[i-1][j-1][k];}}}scanf("%d",&t);while(t--){scanf("%d %d",&n,&k);printf("%d\n",dp[2*n][1][2*k-1]);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！