Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- int n;
- vector<ll> arr;
- ll operation(int l, int r){
- //cout << "l: " << l << ", r: " << r << '\n';
- if(l>r) return 0;
- ll mn = LLONG_MAX;
- for(int i=l; i<=r; i++){
- //cout << "i: " << i << ", arr[i]: " << arr[i] << '\n';
- mn = min(mn, arr[i]);
- }
- //return 0;
- //int start = l;
- for(int i=l; i<=r; i++){
- arr[i]-=mn;
- //if(arr[i]>0){
- //start = i;
- //}
- }
- int start = l;
- ll ops = mn;
- //!!! ops must start equal to mn or else value will always just be 0
- for(int i=l; i<=r; i++){
- //cout << "i: " << i << ", arr[i]: " << arr[i] << '\n';
- //values after erase and if equal to zero then seperate array to go check the seperated part
- if(arr[i] == 0){
- ops+=operation(start, i-1);
- start = i+1;
- }
- }
- ops+=operation(start, r);
- return min((ll)(r-l)+1, ops);
- //at the end compare between operation 1 and operation 2 which operation 2 is just (r-l)+1 because individual
- }
- int main(){
- //freopen("clearmultiset.in", "r", stdin);
- cin >> n;
- //vector<int> arr;
- arr.resize(n+1);
- for(int i=1; i<=n; i++){
- cin >> arr[i];
- }
- cout << operation(1, n) << '\n';
- //cout << "HI" << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
