CUBE-T104: Tasty Chocolate

#include <bits/stdc++.h>
using namespace std;

const int N = 1000;

int arr[N + 1], dp[N + 2][3001];

int main(){

    int nArr;
    scanf("%d", &nArr);
    for(int i = 1; i <= nArr; ++i){
        scanf("%d", &arr[i]);
    }
    for(int i = 1; i <= nArr; ++i){
        dp[i][3000] = 1e9;
    }
    for(int i = nArr; i >= 1; --i){
        for(int x = 2999; x >= 0; --x){
            int ans = 1e9;
            if(arr[i] > x){
                ans = dp[i + 1][arr[i]];
            }
            dp[i][x] = min(ans, 1 + dp[i + 1][x + 1]);
        }
    }
    cout << dp[1][0];

    return 0;
}