Разделить массив на подмассивы так, чтобы сумма произведения их длины и XOR была минимальной

У нас есть массив из «n» чисел. Нам нужно разбить его на M подмассивов так, чтобы стоимость была минимальной.

Стоимость = (XOR подмассива) X (длина подмассива)

Eg: 

array = [11,11,11,24,26,100] 

M = 3

ВЫВОД => 119

Объяснение:

 Dividing into subarrays as = > [11] , [11,11,24,26] , [100]

As 11*1 + (11^11^24^26)*4 + 100*1 => 119 is minimum value.

Eg2: array = [12,12]
     M = 1

output: 0

As [12,12] one way and (12^12)*2 = 0.

arrays algorithm xor sub-array segment-tree
person learner-coder    schedule 10.08.2019    source источник
comment
Хорошо, какова ваша попытка до сих пор?   -  person SomeDude    schedule 10.08.2019
comment
Какую временную сложность вы собираетесь использовать / размер ввода?   -  person Primusa    schedule 11.08.2019
comment
1 ‹= M ‹= 100 и размер массива 1 ‹= n ‹= 1000. Я могу действовать в любом направлении, например рассматривать каждый подмассив, что приводит меня в зону динамического программирования. И чем я не могу понять, как действовать.   -  person learner-coder    schedule 11.08.2019

Ответы (1)


arrow_upward
1
arrow_downward

Вы можете решить эту проблему, используя динамическое программирование.

Определим dp[i][j]: минимальную стоимость решения этой задачи, когда у вас есть только первые i элементов массива и вы хотите разбить (разбить) их на j подмассивов.

dp[i][j] = стоимость последнего подмассива плюс стоимость разбиения другой части данного массива на j-1 подмассив

Это мое решение, которое работает за O(m * n^2):

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000 + 10;
const int MAXM = 1000 + 10;
const long long INF = 1e18 + 10;

int n, m, a[MAXN];
long long dp[MAXN][MAXM];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    // start of initialization
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            dp[i][j] = INF;
    dp[0][0] = 0;
    // end of initialization
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int last_subarray_xor = 0, last_subarray_length = 0;
            for (int k = i; k >= 1; k--) {
                last_subarray_xor ^= a[k];
                last_subarray_length = i - k + 1;
                dp[i][j] = min(dp[i][j], dp[k - 1][j - 1] + (long long)last_subarray_xor * (long long)last_subarray_length);
            }
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

Пример ввода:

6 3
11 11 11 24 26 100

Пример вывода:

119

Одна из самых простых классических задач динамического программирования называется "Рюкзак 0-1". Википедия.

person Erfan Alimohammadi    schedule 24.08.2019