結果
問題 | No.1077 Noelちゃんと星々4 |
ユーザー |
![]() |
提出日時 | 2020-06-12 21:26:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 119 ms / 2,000 ms |
コード長 | 647 bytes |
コンパイル時間 | 3,883 ms |
コンパイル使用メモリ | 196,972 KB |
最終ジャッジ日時 | 2025-01-11 02:10:30 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define modulo 1000000007 #define mod(mod_x) ((((long long)mod_x+modulo))%modulo) #define Inf 1000000005 int main(){ int N; cin>>N; vector<int> Y(N); for(int i=0;i<N;i++){ cin>>Y[i]; Y[i] += 3000; } vector<vector<int>> dp(N,vector<int>(20000,Inf)); for(int i=0;i<N;i++){ int mini = Inf; for(int j=0;j<20000;j++){ if(i==0){ dp[i][j] = abs(Y[i]-j); } else{ mini = min(mini,dp[i-1][j]); dp[i][j] = min(dp[i][j],mini+abs(Y[i]-j)); } } } int ans = Inf; for(int i=0;i<dp.back().size();i++)ans = min(ans,dp.back()[i]); cout<<ans<<endl; return 0; }