Codeforces Beta Round #38 E. Let's Go Rolling!
動的計画法。ビー玉の位置でソートして、左から順に、ビー玉をある位置で止めるときに必要な金を求める。
#include <iostream> #include <vector> #include <utility> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<pair<int,int> > m(n); for ( int i=0; i<n; i++ ) cin >> m[i].first >> m[i].second; sort(m.begin(),m.end()); vector<long long> T(n,10000000000000ll); T[0] = m[0].second; for ( int i=1; i<n; i++ ) { T[i] = *min_element(T.begin(),T.begin()+i) + m[i].second; for ( int j=0; j<i; j++ ) T[j] += m[i].first - m[j].first; } cout << *min_element(T.begin(),T.end()) << endl; }