Cod sursa(job #2215578)

Utilizator AndreiTurcasTurcas Andrei AndreiTurcas Data 22 iunie 2018 17:47:23
Problema Wanted Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#define oo 0x3f3f3f3f
using namespace std;

ifstream f("wanted.in");
ofstream g("wanted.out");

struct town
{
    int x, y;
};
town T[201];
int dp[2][201][201], n;

bool comp(town x, town y)
{
    return x.x < y.x;
}

int dist(int a, int b)
{
    return abs(T[b].x - T[a].x) + T[a].y + T[b].y;
}

int main()
{
    f >> n;
    for(int i = 1; i <= n; ++i)
        f >> T[i].x >> T[i].y;
    sort(T+1, T+n+1, comp);
    for(int i = 2; i <= n; ++i) dp[0][i][i] = dist(i-1, i);
    for(int i = 1; i < n; ++i) dp[1][i][i] = dist(i, i+1);
    for(int d = 2; d < n; ++d)
        for(int i = 1; i <= n-d+1; ++i)
    {
        int j = i +d -1;
        dp[0][i][j] = dp[1][i][j] = oo;

        for(int k = i; k <= j; ++k)
        {
            if(i > 1)
            dp[0][i][j] = min(dp[0][i][j], dist(i-1, k) + max(dp[1][i][k-1], dp[0][k+1][j]));
            if(j < n)
            dp[1][i][j] = min(dp[1][i][j], dist(j+1, k) + max(dp[1][i][k-1], dp[0][k+1][j]));
        }
    }
    int ans = oo;
    for(int k = 1; k <= n; ++k)
        ans = min(ans, dist(0, k) + max(dp[1][1][k-1], dp[0][k+1][n]));
    g << ans << "\n";
}