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

[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, 2023，由reflectK修改

[fangaa]

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

[reflectK]

1 小时前，fangaa说道:

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

第一题应该可以有结论

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

二月 14, 2023，由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, 2023，由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, 2023，由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, 2023，由fangaa修改

[vhet]

看着就有点脑壳疼

[猛男鸽王]

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

[reflectK]

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

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

确实是算法竞赛的题目

[猛男鸽王]

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

[你就得瑟吧]

是用来做游戏的吗？

[冷枫月雨]

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

[古代学者]

下意识求解，等等，我在哪？

[reflectK]

刚刚，古代学者说道:

下意识求解，等等，我在哪？

你在SS同盟

[饿掉鱼]

假设有栖在起点 $(0,0)$，终点在 $(n-1,m-1)$，我们设 $f_{i,j}$ 表示从起点 $(0,0)$ 到 $(i,j)$ 的合法路径数（这里 $i$ 表示横坐标，$j$ 表示纵坐标）。显然，当 $i=0$ 或 $j=0$ 时，$f_{i,j}=1$，因为只能向右或向上移动到达 $(i,j)$。当 $i>0$ 且 $j>0$ 时，有两种情况：

1. 不使用魔法，从 $(i-1,j)$ 转移而来。此时有 $f_{i,j}=f_{i-1,j}+f_{i,j-1}$。

2. 使用魔法，从 $(i+k,j)$ 或 $(i,j+k)$ 转移而来，其中 $k\in[1,\min(i,n-i),\min(j,m-j)]$。因为只能向左或向下转移，而且不能转移到地图外，所以 $k$ 的取值范围为 $\min(i,n-i)$ 和 $\min(j,m-j)$ 的交集。此时有 $f_{i,j}=\sum_{k=1}^{\min(i,n-i)}f_{i-k,j}+\sum_{k=1}^{\min(j,m-j)}f_{i,j-k}$。

最终的答案为 $f_{n-1,m-1}$。

时间复杂度：$O(nm\min(n,m))$。

 

大人时代变了,现在是AI时代

[古代学者]

20 分钟前，reflectK说道:

你在SS同盟

没搞过算法竞赛，不知道我的想法对不对

对于第一个问题，的确就是个动态规划，假设左下角坐标为（0,0），右上角为(m,n)，那么对于任意的i(m>=i>0)，j(n>=j>0)，抵达(i,j)所有可能路线为P(i,j)，那么P(i,j)=P(i-1,j)+P(i,j-1)。

对于第二个问题，因为需要执行一次魔法操作，不妨假定在(i,j)处执行魔法操作，其中i,j不同时为0。假设P(i,j)表示从(0,0)到(i,j)的所有可能路线，Q(i,j)表示(i,j)到(m,n)的所有可能路线，H(i,j)表示在(i,j)处执行魔法操作后对应的全部路线，那么H(i,j) = P(i,j) * (Q(i-1,j)+Q(i,j-1))

[古代学者]

刚刚，古代学者说道:

没搞过算法竞赛，不知道我的想法对不对

对于第一个问题，的确就是个动态规划，假设左下角坐标为（0,0），右上角为(m,n)，那么对于任意的i(m>=i>0)，j(n>=j>0)，抵达(i,j)所有可能路线为P(i,j)，那么P(i,j)=P(i-1,j)+P(i,j-1)。

对于第二个问题，因为需要执行一次魔法操作，不妨假定在(i,j)处执行魔法操作，其中i,j不同时为0。假设P(i,j)表示从(0,0)到(i,j)的所有可能路线，Q(i,j)表示(i,j)到(m,n)的所有可能路线，H(i,j)表示在(i,j)处执行魔法操作后对应的全部路线，那么H(i,j) = P(i,j) * (Q(i-1,j)+Q(i,j-1))

对于第三个问题，如果经过A则必须经过B，那么所有可能路线是第一个问题的解减去经过A而没经过B的所有路径，设Pa0表示从原点到A所有可能路径，Pa表示从A到终点所有可能路径，Pab表示从A到B所有可能路径，Pb表示从B到终点左右可能路径，P为第一个问题的解，本问题解为Q，则Q = P - Pa0 * (Pa - Pa * Pab * Pb)

如果经过A则强制穿越到B，那么AB绑死，所以所有可能路径是第一个问题的解减去所有经过A的解，再加上原点到A的所有可能路径与B到终点所有可能路径的乘积

如果不能同时经过A和B，那么所有可能路径是第一个问题的解减去同时经过AB的所有路径，后者是所有从原点到A的路径、A到B所有路径、B到终点所有路径的乘积

[reflectK]

1 小时前，饿掉鱼说道:

假设有栖在起点 $(0,0)$，终点在 $(n-1,m-1)$，我们设 $f_{i,j}$ 表示从起点 $(0,0)$ 到 $(i,j)$ 的合法路径数（这里 $i$ 表示横坐标，$j$ 表示纵坐标）。显然，当 $i=0$ 或 $j=0$ 时，$f_{i,j}=1$，因为只能向右或向上移动到达 $(i,j)$。当 $i>0$ 且 $j>0$ 时，有两种情况：

1. 不使用魔法，从 $(i-1,j)$ 转移而来。此时有 $f_{i,j}=f_{i-1,j}+f_{i,j-1}$。

2. 使用魔法，从 $(i+k,j)$ 或 $(i,j+k)$ 转移而来，其中 $k\in[1,\min(i,n-i),\min(j,m-j)]$。因为只能向左或向下转移，而且不能转移到地图外，所以 $k$ 的取值范围为 $\min(i,n-i)$ 和 $\min(j,m-j)$ 的交集。此时有 $f_{i,j}=\sum_{k=1}^{\min(i,n-i)}f_{i-k,j}+\sum_{k=1}^{\min(j,m-j)}f_{i,j-k}$。

最终的答案为 $f_{n-1,m-1}$。

时间复杂度：$O(nm\min(n,m))$。

 

大人时代变了,现在是AI时代

但是对于所有的i=0/j=0 也可以用魔法进行转移吧w

[reflectK]

41 分钟前，古代学者说道:

对于第三个问题，如果经过A则必须经过B，那么所有可能路线是第一个问题的解减去经过A而没经过B的所有路径，设Pa0表示从原点到A所有可能路径，Pa表示从A到终点所有可能路径，Pab表示从A到B所有可能路径，Pb表示从B到终点左右可能路径，P为第一个问题的解，本问题解为Q，则Q = P - Pa0 * (Pa - Pa * Pab * Pb)

如果经过A则强制穿越到B，那么AB绑死，所以所有可能路径是第一个问题的解减去所有经过A的解，再加上原点到A的所有可能路径与B到终点所有可能路径的乘积

如果不能同时经过A和B，那么所有可能路径是第一个问题的解减去同时经过AB的所有路径，后者是所有从原点到A的路径、A到B所有路径、B到终点所有路径的乘积

差不多就是这样吧www 挺好的

[ak47bad]

算了一会儿，我不是在逛sstm吗……为什么会被勾起数学方面的胜负欲啊摔！