arrays - 将一个数组分成子数组，使它们的长度与异或的乘积之和最小

Question

我们有一个包含“n”个数字的数组。我们需要将它分成 M 个子数组，使得成本最小。

成本=(子数组的异或)X(子数组的长度)

例如:

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. 

Answer 1

您可以使用动态规划来解决这个问题。

让我们定义 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 背包”，可在 Wikipedia 上找到。 .