Sort the quarters that can be crossed.And then dp.

The state transition equation is
F[i]=Max{ F[j] + 1 | P[j].x<P[i].x and P[j].y<P[i].y }

The maximum of F[i] is the number of the the quarters that should be crossed.

Then you can work out the answer.

Edited by moderator 18.08.2020 02:22

A solution for Chinese readers.Much clearer.

这道题有明显的动态规划策略。首先不要按照方格来考虑，考虑顶点，这样目标点就是(N+1,M+1)。

---------算法1-----------
最直观的想法是按照矩阵动态规划。

设状态F[i,j]为走到点(i,j)时的最短路径

状态转移方程
F[i,j]=Min
{
F[i-1,j]+100
F[i,j-1]+100
F[i-1,j-1]+141.4213562373
}

边界条件 F[0,0]=0

F[N+1,M+1]就是结果。

但是对于8M的内存限制，要使用滚动数组。

时间复杂度为O(N*M)

---------算法2-----------
可以发现，如果我们只走直边的话，要走(N+M)*100长度。如果走C条斜边，那么要走(C*141.4213562373)+(N+M-C*2)*100 的长度。那么显然我们要尽可能使C更大，即多走斜边。

这样可以转化为经典的LIS模型。即把所有的斜边按照坐标排序，然后求最长的上升序列(x，y都要严格递增)，走这样的斜边一定是最优的策略。于是我们可以求出C。

结果就是(C*141.4213562373)+(N+M-C*2)*100。

Vijos 1336其实就是这道题的数据加大版。对于较小的K和很大的N,M，只能用算法2解决。

by translating.............

A solution for Chinese readers.Much clearer.

This problem has obvious dynamic programming strategies. First, don't think in terms of squares, consider vertices, so the target point is (N + 1, M + 1).

--------- Algorithm 1 -----------
The most intuitive idea is dynamic programming in terms of matrices.

Let the state F [i, j] be the shortest path to the point (i, j)

State transition equation
F [i, j] = Min
{
F [i-1, j] +100
F [i, j-1] +100
F [i-1, j-1] +141.4213562373
}

Boundary condition F [0,0] = 0

F [N + 1, M + 1] is the result.

But for the 8M memory limit, a rolling array is used.

Time complexity is O (N * M)

--------- Algorithm 2 -----------
It can be found that if we only go straight, we have to go to (N + M) * 100 length. If you take the C hypotenuse, then you have to take the length of (C * 141.4213562373) + (N + M-C * 2) * 100. So obviously we want to make C as large as possible, that is, take more hypotenuse.

This can be transformed into a classic LIS model. That is, sort all the hypotenuses according to the coordinates, and then find the longest ascending sequence (x, y must be strictly increased). Taking such hypotenuses must be the optimal strategy. Then we can find C.

The result is (C * 141.4213562373) + (N + M-C * 2) * 100.

Vijos 1336 is actually an enlarged version of this question. For smaller K and large N, M, it can only be solved by algorithm 2.