結果
問題 | No.1077 Noelちゃんと星々4 |
ユーザー |
![]() |
提出日時 | 2020-06-12 22:41:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 12 ms / 2,000 ms |
コード長 | 1,356 bytes |
コンパイル時間 | 428 ms |
コンパイル使用メモリ | 46,276 KB |
実行使用メモリ | 14,976 KB |
最終ジャッジ日時 | 2024-06-24 05:26:37 |
合計ジャッジ時間 | 1,369 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <cstdio> #include <algorithm> using namespace std; typedef long long int64; const int MAX_N = 2000; const int64 INF = 1LL<<60; int N; int64 as[MAX_N], bs[MAX_N]; int64 dp[MAX_N + 1][MAX_N]; void init() { scanf("%d", &N); for (int i = 0; i < N; ++i) { scanf("%lld", as+i); } } int solve() { int64 ans = INF; for (int i = 0; i < N; ++i) { bs[i] = as[i]; } sort(bs, bs + N); //inc for (int i = 0; i <= N; ++i) { fill(dp[i], dp[i] + N, (i ? INF : 0)); } for (int i = 0; i < N; ++i) { int64 mini = INF; for (int h = 0; h < N; ++h) { dp[i+1][h] = min<int64>( dp[i+1][h], dp[i][h] + abs(as[i] - bs[h]) ); if (as[i] >= bs[h]) { dp[i+1][h] = min<int64>( dp[i+1][h], mini + abs(as[i] - bs[h]) ); mini = min( mini, dp[i][h] ); } } } ans = min( ans, *min_element(dp[N], dp[N] + N) ); /* //dec for (int i = 0; i <= N; ++i) { fill(dp[i], dp[i] + N, (i ? INF : 0)); } for (int i = 0; i < N; ++i) { int64 mini = INF; for (int h = N - 1 ; h >= 0; --h) { dp[i+1][h] = min<int64>( dp[i+1][h], dp[i][h] + abs(as[i] - bs[h]) ); if (as[i] <= bs[h]) { dp[i+1][h] = min<int64>( dp[i+1][h], mini + abs(as[i] - bs[h]) ); mini = min( mini, dp[i][h] ); } } } ans = min( ans, *min_element(dp[N], dp[N] + N) ); */ return (int)ans; } int main() { init(); printf("%d\n", solve()); return 0; }