Cod sursa(job #605366)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 28 iulie 2011 00:14:23
Problema Wanted Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <iostream>
#include <cstdio>
#include <algorithm>

#define NMax 205
#define Inf 2000000005

using namespace std;

typedef struct
{
    int X;
    int Y;
}
Coord;

Coord City[NMax];
int N, Best[NMax][NMax][2];

void Read ()
{
    freopen ("wanted.in", "r", stdin);
    scanf ("%d", &N);
    for (int i=1; i<=N; ++i)
    {
        scanf ("%d %d", &City[i].X, &City[i].Y);
    }
}

inline int Min (int a, int b)
{
    if (a<b)
    {
        return a;
    }
    return b;
}

inline int Max (int a, int b)
{
    if (a>b)
    {
        return a;
    }
    return b;
}

inline int Dist (int a, int b)
{
    if (a==b)
    {
        return 0;
    }
    return (City[a].Y+City[b].Y+Max (City[a].X-City[b].X, City[b].X-City[a].X));
}

int Memo (int L, int R, int P)
{
    if (L>R)
    {
        Best[L][R][P]=0;
        return 0;
    }
    if (Best[L][R][P]<Inf)
    {
        return Best[L][R][P];
    }
    for (int i=L; i<=R; ++i)
    {
        if (P==0)
        {
            Best[L][R][P]=Min (Best[L][R][P], Max (Memo (L, i-1, 1), Memo (i+1, R, 0))+Dist (L-1, i));
        }
        else
        {
            Best[L][R][P]=Min (Best[L][R][P], Max (Memo (L, i-1, 1), Memo (i+1, R, 0))+Dist (i, R+1));
        }
    }
    return Best[L][R][P];
}

void Print ()
{
    freopen ("wanted.out", "w", stdout);
    printf ("%d\n", Memo (1, N, 0));
}

inline bool cmp (Coord A, Coord B)
{
    if (A.X<B.X)
    {
        return true;
    }
    return false;
}

int main()
{
    Read ();
    sort (City+1, City+N+1, cmp);
    for (int i=0; i<=N; ++i)
    {
        for (int j=0; j<=N; ++j)
        {
            Best[i][j][0]=Best[i][j][1]=Inf;
        }
    }
    Print ();
    return 0;
}