結果
問題 | No.1077 Noelちゃんと星々4 |
ユーザー |
![]() |
提出日時 | 2020-06-12 21:50:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 29 ms / 2,000 ms |
コード長 | 814 bytes |
コンパイル時間 | 1,609 ms |
コンパイル使用メモリ | 169,164 KB |
実行使用メモリ | 42,856 KB |
最終ジャッジ日時 | 2024-06-24 04:50:47 |
合計ジャッジ時間 | 2,930 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define REP(i,a,n) for(int i=(a); i<(int)(n); i++) #define rep(i,n) REP(i,0,n) #define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it) #define ALLOF(c) (c).begin(), (c).end() typedef long long ll; typedef unsigned long long ull; static const int INF = 1e9; int dp[1005][10005]; int main(){ int N; cin >> N; vector<int> v; rep(i,N){ int a; cin >> a; v.push_back(a); } rep(i,1005) rep(j,10005) dp[i][j] = INF; rep(i,10005){ dp[0][i] = abs(i - v[0]); } REP(i,1,N){ int mn = dp[i-1][0]; rep(j,10005){ mn = min(mn, dp[i-1][j]); dp[i][j] = abs(j - v[i]) + mn; } } int ret = dp[N-1][0]; rep(i,10005){ ret = min(ret, dp[N-1][i]); } cout << ret << endl; return 0; }