CodeForces Beta Round #19 B. 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; }