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; } };