CodeForces Beta Round #19 B. Checkout Assistant

Checkout Assistant

コンテスト中はk番目までの商品でm秒の余裕を作るのに必要な最小のお金を求めるDPでプログラムを書いていた。配列の添字が負値にもなって面倒だなと思っていたら、mにレジを通過した商品数も加えれば負にはならないと教わった。たしかに。

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;  cin >> n;

    vector<vector<long long> > money( n+1,
        vector<long long>( n+1, n*1000000000ll ) );
    money[0][0] = 0;
    
    for ( int k=0; k<n; k++ )
    {
        int t, c;  cin >> t >> c;

        for ( int m=0; m<=n; m++ )
        {
            int mt = min( m+t+1, n );
            money[k+1][mt] = min( money[k+1][mt], money[k][m] + c );
            money[k+1][m ] = min( money[k+1][m ], money[k][m] );
        }
    }

    cout << money[n][n] << endl;
}