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