제출 #675556

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
675556		brijeshSiwach	Bigger segments (IZhO19_segments)	C++17	0 / 100	0 ms	212 KiB

segments

#include <iostream>
#include <algorithm>

using namespace std;

const int INF = 1000000000;  // Large constant to represent infinity

// Function to find the minimum number of operations required to make the array non-decreasing
int minimumOperations(int arr[], int n) {
    // Initialize the 2D array for dynamic programming
    int dp[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dp[i][j] = INF;  // Initialize all entries to infinity
        }
        dp[i][i] = 0;  // Set the base case for single elements
    }

    // Use a nested loop to fill in the rest of the array
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i < n - len + 1; i++) {
            int j = i + len - 1;
            // Find the minimum number of operations needed to merge the left and right subarrays
            for (int k = i; k < j; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);
            }
            // If the current subarray is not already non-decreasing, perform an operation
            if (arr[j] < arr[j-1]) {
                dp[i][j]++;
            }
        }
    }

    // Return the minimum number of operations needed for the entire array
    return dp[0][n-1];
}

int main() {
    // Read the array from the user
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // Print the result
    cout << minimumOperations(arr, n) << endl;

    return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27