結果

問題 No.1077 Noelちゃんと星々4
コンテスト
ユーザー rieaaddlreiuu
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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;
}
0