娱乐 （红包）算法挑战一则——到达终点的方法种类

[reflectK]

大家好，这里是reflectK

首先来一道基础题热热身吧~

一个由n*m个方格组成的地图，有栖从左下角的端点走到右上角的端点，只能向上向右走，那么一共有多少种不同的路线？

裸dp，是吧（）

 

然后是两道变体：

一个由n*m个方格组成的地图，有栖从左下角的端点移动到右上角的端点。

有栖可以进行两种操作：

1.移动到右边或是上面相邻的一个端点。

2.使用魔法，可以把有栖的位置向左或者向下转移一格。（注意不能转移出地图外）

一个路线是合法的，当且仅当：

通过这个路线最后可以到达终点，

且恰好使用一次魔法。

如果有栖按照两个路线行动存在一个时刻位置不同，那么称这两个路线是不同的。

那么一共有多少种不同的合法路线？

 

 

一个由n*m个方格组成的地图，有栖从左下角的端点走到右上角的端点，只能向上向右走。

与此同时，规定坐标A(x,y),B(x',y')（m>x'>x>1,n>y'>y>1）是特别的。

求一共有多少种不同的合法路线，当：

1.如果经过了A就必须经过B。

2.如果经过了A会被强制传送到B。

3.不能同时经过A和B。

二月 13，由reflectK修改

[fangaa]

用Dp倒是不难，不过你要的是数学结论吗？

[reflectK]

1 小时前，fangaa说道:

用Dp倒是不难，不过你要的是数学结论吗？

第一题应该可以有结论

第二题只需要dp方程就可以了

二月 14，由reflectK修改

[Jerryxxw]

说下看完题后脑子里的第一手想法，感觉比较繁琐

原题dp[][]

第一个变种，再加一维dp[][][0~1]表示经过该点且是否使用过魔法，递推关系就多考虑一个向左或者向下过来的情况

dp[i][j][0] = dp[i+1][j][0] + dp[i][j - 1][0] dp[i][j][1] = dp[i+1][j][1] + dp[i][j - 1][1] + dp[i - 1][j][0] + dp[i][j + 1][0](合法情况下)

最后返回右上角dp[][][1]的值

第二个变种，同样是加限制条件[A][B]表示已经经过了A或B [AB]表示已经经过了[AB] []表示两个都没经过，然后根据条件筛选右上角dp的值

(好蠢的思路，空间开销巨大，而且一眼望过去变种2里的条件1和2好像是一个意思？是我考虑不全)

二月 14，由Jerryxxw修改
错别字

[fl-0]

尝试用组合数学来思考的话
第一题可以使用一次魔法感觉就是向上或者向右多走一次--C(n+m+1,n+1)+C(n+m+1,m+1)
第二题经过A必须经过B可以是先走到A再走到B再走到终点--C(x+y,x)*C(x'-x+y'-y,x'-x)*C(n-x'+m-y',n-x')，经过了A会被强制传送到B可以分为两种情况（走A传送到B再走到终点，不走A到终点--总方案减去走A的方案）--C(x+y,x)*C(n-x'+m-y',n-x')+C(n+m,n)-(C(x+y,x)*C(n-x+n-y,n-x))，不能同时经过A和B就是总方案数减去同时经过A和B的方案数（第一种情况）--C(n+m,n)-(C(x+y,x)*C(x'-x+y'-y,x'-x)*C(n-x'+m-y',n-x'))
感觉还有点小bug...

二月 14，由fl-0修改
bug

[fangaa]

7 小时前，reflectK说道:

第一题应该可以有结论

第二题只需要dp方程就可以了

那就是两个函数：f(m,n)是走一个mXn网格的路径数，g(m,n,x,y)是走一个mXn网格但不经过点(x,y)的路径数。那么f(m,n)=C(m+n,m)，而g(m,n,x,y)=f(m,n)-f(x,y)*f(m-x,n-y)。

那后三个就是

1. f(x,y)*f(x'-x,y'-y)*f(m-x',n-y')+g(m,n,x,y)

2. f(x,y)*f(m-x',n-y')+g(m,n,x,y)

3. f(m,n)-f(x,y)*f(x'-x,y'-y)*f(m-x',n-y')

反倒是魔法那个麻烦点，干脆想成mXnX3三层立体的。从中间层开始，上面那层整体向上移一格，下面那层整体向右移一格，然后就正常DP~

二月 14，由fangaa修改

[vhet]

看着就有点脑壳疼

[猛男鸽王]

好家伙，看到这种题，就想起NOI的算法……

[reflectK]

1 分钟前，猛男鸽王说道:

好家伙，看到这种题，就想起NOI的算法……

确实是算法竞赛的题目

[猛男鸽王]

为什么我在这里也能看到算法题啊QAQ

[你就得瑟吧]

是用来做游戏的吗？

[冷枫月雨]

。。。关于我刚复习完然后逛黄油论坛突然看到题目的这件事？