ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
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.

---------算法1-----------

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

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

---------算法2-----------

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.