ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1119. Metro

An O(K^2) solution
Posted by CmYkRgB123 31 Oct 2008 18:11
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.

#include <iostream>

using namespace std;

const int MAX=1002;
const double Dc=141.42135623730950488016887242097;
const double Dl=100.0;
const double INF=1e20;

struct Point
{
    int x,y;
};

int M,N,P;
Point T[MAX];
int F[MAX];
double Ans;

inline int cmp(const void *a,const void *b)
{
    if (((Point *)a)->x==((Point *)b)->x && ((Point *)a)->y<((Point *)b)->y)
        return -1;
    return ((Point *)a)->x < ((Point *)b)->x ?-1 :1;
}

void init()
{
    int i,a,b;
    cin >> M >> N >> P;
    N++;M++;
    for (i=1;i<=P;i++)
    {
        cin >> b >> a;
        a++;b++;
        T[i].x=a;
        T[i].y=b;
    }
    qsort(T+1,P,sizeof(T[0]),cmp);
}

void dynamic()
{
    int i,j,max,cnt=0,d;
    for (i=1;i<=P;i++)
    {
        max=0;
        for (j=0;j<=i-1;j++)
        {
            if (T[j].x<T[i].x && T[j].y<T[i].y &&  F[j] + 1 > max)
                max=F[j]+1;
        }
        F[i]=max;
        if (F[i]>cnt)
            cnt=F[i];
    }
    d=N+M-cnt*2-2;
    Ans=d*Dl + cnt*Dc;
    printf("%.0lf",Ans);
}

int main()
{
    init();
    dynamic();
    return 0;
}
Re: An O(K^2) solution
Posted by CmYkRgB123 31 Oct 2008 18:26
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解决。
Re: An O(K^2) solution
Posted by abid1729 30 Mar 2020 23:12
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.