Codeforces Good Bye 2014 C, New Year Book Reading
問題
http://codeforces.com/contest/500/problem/C
本が N (< 500) 冊ある. それぞれの本には重さがある. 本は全て重ねて積んだ状態である. 上から I 番目の本を読む場合には, I 番目の本を取り出して山の一番上に移動させる. この時, あなたには 1~I-1 番目の本の重量分の負荷がかかる.
M (< 1000) 日間, 1 日 1 冊の本を読みたい. I 日目に読む本は b[i] で与えられる. 同じ本を複数の日に読む場合もある. M 日間の負荷の最小値を求めよ.
方針
読み終わった本を上に重ねるので, 新しい本 B を読む場合の負荷は「B より前に読んだ本の重さ + B の上にある未読本の重さ」となる. 本を初めて読む順番で積んでおけば, 後者がゼロになる.
解答
int main(int argc, char const* argv[]) { int n, m; cin >> n >> m; vector<int> weight(n), b(m); loop (n, i) cin >> weight[i]; loop (m, i) { cin >> b[i]; b[i]--; } vector<int> order; loop (m, i) if (find(all(order), b[i]) == order.end()) { order.push_back(b[i]); } int ans = 0; loop (m, i) { int j = 0; while (order[j] != b[i]) { ans += weight[order[j]]; j++; } order.erase(order.begin()+j); order.insert(order.begin(), b[i]); } cout << ans << endl; return 0; }