Codeforces Beta Round #38 E. Let's Go Rolling!

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