logoChat01.ai

You are given an array a [1..N] of positive intege...

Criado em: 26 de abril de 2026

Respondido usando GPT-5.5 Thinking por Chat01

Pergunta

You are given an array a [1..N] of positive integers, partitionit into exactly K contiguous blocks. The cost of a block a[l..r] depends on its length len = r-1+1: alias

If len is odd: cost = len x max(a[l..r])

If len is even: cost = len x min(a[l..r])

Find the minimum total cost across all K blocks.

Input Format

danish0666

The first line contains a integer, n, denoting the size of the array.

The second line contains a integer, k, denoting the exact number of contiguous blocks.

Each line i of the n subsequent lines (where 0 ≤ i < n) contains a integer,

a[i].

Constraints

1 <= n <= 500

1 <= k <= 500

danish.

1 <= a[i] <= 10 ^ 4

Sample Test Cases

Case 1

Input:

4

2

alidanish0666

57

2

8

3

Output:

10

alidanish0966

E

Explanation:

n = 4 k = 2 a = [5, 2, 8, 3] Optimal split: [5,2] | [8,3] [5,2] length 2 (even) 2min(5, 2) = 2 * 2 = 4[8, 3] \rightarrow [ength 2(even) 2min(8, 3) = 2 * 3 = 6 Total 4+6 = 10

Case 2

Input:

5

3

1

10

1

10

1

alidanish0666

Output:

5

Explanation:

ch0666

n=5, k=3, a=[1,10,1,10,1] Optimal split: [1] | [10,1] | [10,1] [1] → length 1 (odd) 1 x max(1) = 1 [10,1] → length 2 (even) 2 x min (10,1) = 2x12 [10,1] min(10,1) length 2 (even) + 2 x 2x12 Total 1+2+2 = 5

Case 3

Input:

6

3

3

1
4
1
5
9
Output

8

anish 0166

Explanation:

1 [ Split: [3] | [4,1,5,9] [3]→

odd, cost = 1x3 = 3 [1] 1x11 [4,1,5,9] even odd, cost = (len=4), cost

=4xmin=4x14 Total 3+1+4 = 8
#include <bits/stdc++.h>

using namespace std;

int solve(int n, int k, vector<int>& a) {

// Write your solution here

}

int main() {

ios_base::sync_with_stdio(false);

cin.tie(NULL);

int n; if (!(cin >> n)) return 0;

int k; if (!(cin >> k)) return 0;

vector<int> a(n);

for (int i = 0; i < n; i++) if (!(cin >> a[i])) retu

auto result = solve(n, k, a);

cout << result << endl;

return 0;

}
Please give me proper code without explanation also I mentioned in the last

Pensamento

Considering constraints and the solution approach

The task calls for a C++ solution to partition an array into exactly K blocks with specific costs. I’ll ensure the code handles values like K and N up to 500 and maximizes computational efficiency. Given the complexity, I'll use dynamic programming and long long handling to avoid overflow. Additionally, I’ll account for any potential input issues that may arise.

Thought for 10s

Resposta

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

int solve(int n, int k, vector<int>& a) {
    if (k > n) return -1;

    vector<vector<long long>> cost(n + 1, vector<long long>(n + 1, 0));

    for (int l = 1; l <= n; l++) {
        int mn = INT_MAX, mx = INT_MIN;
        for (int r = l; r <= n; r++) {
            mn = min(mn, a[r - 1]);
            mx = max(mx, a[r - 1]);

            int len = r - l + 1;
            if (len % 2 == 1) {
                cost[l][r] = 1LL * len * mx;
            } else {
                cost[l][r] = 1LL * len * mn;
            }
        }
    }

    const long long INF = 4e18;
    vector<vector<long long>> dp(k + 1, vector<long long>(n + 1, INF));

    dp[0][0] = 0;

    for (int blocks = 1; blocks <= k; blocks++) {
        for (int i = blocks; i <= n; i++) {
            for (int prev = blocks - 1; prev < i; prev++) {
                dp[blocks][i] = min(dp[blocks][i], dp[blocks - 1][prev] + cost[prev + 1][i]);
            }
        }
    }

    return (int)dp[k][n];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int k;
    cin >> k;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    cout << solve(n, k, a) << '\n';

    return 0;
}

Compartilhar esta Q&A