logoChat01.ai

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

생성일: 2026년 4월 26일

답변에 사용된 모델 GPT-5.5 Thinking by Chat01

질문

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

사고

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

답변

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

이 Q&A 공유하기