MHGOC05 - Editorial

editorial
, , ,
1

Question:

Two Robots

Difficulty level

Easy

Prerequisites

None

Code

include < iostream >
include < sstream >
include < fstream >
include < vector >
include < cmath >
include < algorithm >

using namespace std;

define FOR(i,a,b) for(int i=a; i<=b; ++i)

const int MAX = 1e+9;
int dp[1001][1001];

class Test
{
public:
int m;
vector a, b;
int solve()
{
int n = a.size();
if (n == 0) return 0;
FOR(i, 2, n)
FOR(j, 1, m)
dp[i][j] = MAX;

    FOR(j, 1, m)  
        dp[1][j] = abs(b[0] - a[0]);  

    FOR(i, 2, n)  
        FOR(j, 1, m)  
    {  
        dp[i][b[i - 2]] = min(dp[i][b[i-2]], dp[i-1][j] + abs(j - a[i-1]) + abs(a[i-1] - b[i-1]));  
        dp[i][j] = min(dp[i][j], dp[i-1][j] + abs(b[i-2] - a[i-1]) + abs(a[i-1] - b[i-1]));  
    }  
    int sol = MAX;  
    FOR(j, 1, m)  
        sol = min(sol, dp[n][j]);  
    return sol;  
}  
friend istream & operator >> (istream & is, Test & test)  
{  
    int n;  
    is >> test.m >> n;  
    FOR(i, 1, n)  
    {  
        int a, b;  
        is >> a >> b;  
        test.a.push_back(a);  
        test.b.push_back(b);  
    }  
    return is;  
}

};

vector tests;

int main()
{
int t;
cin >> t;
while (t–)
{
Test test;
cin >> test;
cout << test.solve() << endl;
}
return 0;
}