結果
問題 |
No.1077 Noelちゃんと星々4
|
ユーザー |
![]() |
提出日時 | 2020-07-05 16:51:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 85 ms / 2,000 ms |
コード長 | 852 bytes |
コンパイル時間 | 795 ms |
コンパイル使用メモリ | 75,992 KB |
最終ジャッジ日時 | 2025-01-11 15:58:53 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <iostream> #include <vector> using namespace std; using vi = vector<int>; #define rep(i,n) for(int i=0,_i=(n);i<_i;++i) int main() { int N; cin >> N; vi Y(N); int max_Y = 0; rep(i, N) { cin >> Y[i]; max_Y = max(max_Y, Y[i]); } vector<vi> dp(N+1, vi(10001, 0)); // i番目まで広義単調増加にしたとき、i番目の高さがj vector<vi> dp_min(N+1, vi(10001, 1e9)); // i番目まで広義単調増加にしたとき、i番目の高さがj rep(i, max_Y+1) dp_min[0][i] = 0; rep(i, N) { rep(j, max_Y+1) { dp[i+1][j] = dp_min[i][j] + abs(Y[i] - j); if (j > 0) dp_min[i+1][j] = min(dp_min[i+1][j-1], dp[i+1][j]); else dp_min[i+1][j] = dp[i+1][j]; } } int ans = 1e9; rep(i, max_Y+1) { ans = min(ans, dp[N][i]); } cout << ans << endl; return 0; }