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

[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修改

[reflectK]

1 小时前，fangaa说道:

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

第一题应该可以有结论

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

二月 14, 2023，由reflectK修改

[reflectK]

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

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

确实是算法竞赛的题目

[reflectK]

刚刚，古代学者说道:

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

你在SS同盟

[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 挺好的