Topcoder SRM 719 Div1 Easy - LongMansionDiv1

問題概要

N行無限列の2次元グリッドがある。各行にはコストが設定されており、その行のマスに1回乗るたびに毎回そのコストがかかる。移動の開始点と終了点が与えられるので最小のコストを求めよ。

N <= 50

解法

開始行→経由行→終了列→終了行という感じで移動することを考えて、経由行を全探索する。O(N).

感想

まじでこれ以上書くことがない

コード (C++)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;

class LongMansionDiv1 {
public:
    ll minimalTime(vector<int> t, int sX, int sY, int eX, int eY) {
        int N = t.size();
        ll ans = 1LL << 59;
        
        for (int x = 0; x < N; ++x) {
            ll tmp = (ll)abs(eY - sY) * t[x];
            for (int i = min(x, sX); i <= max(x, sX); ++i) tmp += t[i];
            for (int i = min(x, eX); i <= max(x, eX); ++i) tmp += t[i];
            tmp -= t[x];
            ans = min(ans, tmp);
        }

        return ans;
    }
};