結果
問題 |
No.1077 Noelちゃんと星々4
|
ユーザー |
![]() |
提出日時 | 2024-12-06 01:00:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 57 ms / 2,000 ms |
コード長 | 998 bytes |
コンパイル時間 | 1,784 ms |
コンパイル使用メモリ | 171,064 KB |
実行使用メモリ | 42,368 KB |
最終ジャッジ日時 | 2024-12-06 01:01:00 |
合計ジャッジ時間 | 3,476 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include<bits/stdc++.h> using namespace std; const int Y_MAX = 10000; int min_compare(int x,int y){ if(x<y){ return x; } return y; } int main(){ int N; cin >> N; vector<int> Y(N+1); for(int i=1;i<=N;i++){ cin >> Y[i]; } vector<vector<int>> dp(N+1,vector<int>(Y_MAX+1)); for(int i=0;i<=Y_MAX;i++){ dp[1][i] = abs(Y[1]-i); } int min; for(int n=2;n<=N;n++){ for(int y=0;y<=Y_MAX;y++){ //dp[n][y]求めるよ if(y == 0){ dp[n][y] = dp[n-1][0]+Y[n]; } else if(y <= Y[n]){ dp[n][y] = min_compare(dp[n][y-1],dp[n-1][y]+abs(Y[n]-y+1)) -1; } else { dp[n][y] = min_compare(dp[n][y-1],dp[n-1][y]+abs(Y[n]-y+1)) +1; } } } int min_result = 998244353; for(int y=0;y<=Y_MAX;y++){ if(min_result > dp[N][y]){ min_result = dp[N][y]; } } cout << min_result << endl; }