codeforces #38

些細なミスでE問題を落としてしまったのが悲しい。
配列のサイズには気をつける。

E問題

ボールがn個あって、それぞれについてx座標とピンを刺すコストcが与えられる。ピンが刺さっているボールはその場で動かず、刺さってないボールは、自分の左にあるピンが刺さっているボールまで動く。ピンを刺すボールをうまく選んで、コストと移動距離の和を最小にし、その時の最小値を求める。
i番目のボールまでで最後にピンを指したボールがj番目のときの最小値をDP[i][j]として二重ループを回すとうまくいきました。
DP[0][0] = MIN[0] =c[0]
DP[i][j] = DP[i-1][j] + |x_i-x_i| (i > j)
DP[i][j] = MIN[i-1] + c_i (i = j)
MIN[i] = min(DP[i][0], ... , DP[i][i])
といったかんじ。
バグ取りに苦戦して無駄にlong long書いてて見苦しいです。原因は dp[3001][2]と宣言してたことですけどね。

long long dp[3001][3001];
long long mi[3001];
int main(void){
  int n;
  cin>>n;
  vector< pair<long long, long long> > input;
  REP(i,n){
    long long a,b;
    cin>>a>>b;
    input.push_back(pair<long long,long long>(a,b));
  }
  sort(input.begin(), input.end());
  REP(i,3001) mi[i]=100000000000000000;
  dp[0][0] = (long long)input[0].second;
  mi[0] = (long long)input[0].second;
  FOR(i,1,n){
    FOR(j,0,i){
      dp[i][j] = (long long)dp[i-1][j] + (long long)abs((long long)input[i].first-input[j].first);
      mi[i] = (long long)min(mi[i], dp[i][j]);
    }
    dp[i][i] = (long long)mi[i-1] + (long long)input[i].second;
    mi[i] = (long long)min(mi[i], dp[i][i]);
  }
  cout<<mi[n-1]<<endl;
  return 0;
}