algorithm - 基于动态规划之字形拼图

Question

我发现了这个有趣的动态规划问题，它需要对整数序列重新排序以最大化输出。

史蒂夫有 N 个酒瓶。 第 th 瓶的酒精量由 A[i] 给出。现在他想从每个瓶子里喝一杯，这样可以最大限度地消除宿醉。总宿醉计算如下(假设“酒精数量”数组使用基于 1 的索引):

int hangover=0 ;
for( int i=2 ; i<=N ; i++ ){
    hangover += i * abs(A[i] - A[i-1]) ;
}

因此，很明显，他喝每瓶酒的顺序会改变宿醉总量。他可以按任何顺序喝酒，但每瓶酒不能超过一杯。此外，一旦他开始喝一种酒，他就会先喝完那杯酒，然后再喝另一种酒。

史蒂夫不知道他应该按照什么顺序喝酒，这样才能最大限度地解酒。如果他可以按任何顺序喝酒，请帮助他找到最大程度的宿醉。

输入格式:第一行包含测试用例的数量 T。每个测试用例的第一行包含N，表示水果的数量。下一行包含 N 个空格分隔的整数，表示每个水果的甜度。

2
7
83 133 410 637 665 744 986
4
1 5 9 11

我已尽我所能，但无法实现复杂度为 O(n^2) 的解决方案。通过简单地计算所有排列的总宿醉具有 O(n!) 时间复杂度。能否更有效地解决这个问题？

谢谢!

Answer 1

我的直觉:使用一种“贪婪链接算法”而不是 DP。

1) 找到差异最大的对 (O(n^2))

2) 从其中一个开始，依次找到下一个差异最大的元素，形成一种“链”(2 x O(n^2))

3) 一旦你对两者都完成了，你就会有两个“总和”。返回最大的一个作为您的最佳答案。

这种贪心策略应该有效，因为问题本身的本质是贪心的:为最后一瓶选择最大的差异，因为它具有最大的索引，所以结果总是大于一些“妥协”的选择(一个将较小但大致均匀的差异分布到指数)。

复杂度:O(3n^2)。可以概率。如果您使用链接列表而不是静态数组 + bool 标志数组，则将其减少到 O(3/2 n^2)。

伪代码:

int hang_recurse(int* A, int N, int I, int K, bool* F)
{
    int sum = 0;
    for (int j = 2; j <= N; j++, I--)
    {
        int maxdiff = 0, maxidx;
        for (int i = 1; i <= N; i++)
        {
            if (F[i] == false)
            {
                int diff = abs(F[K] - F[i]);
                if (diff > maxdiff)
                {
                    maxdiff = diff;
                    maxidx = i;
                }
            }
        }
        K = maxidx;
        F[K] = true;
        sum += maxdiff * I;
    }
    return sum;
}

int hangover(int* A, int N)
{
    bool* F = new bool[N];
    int maxdiff = 0;
    int maxidx_i, maxidx_j;
    for (int j = 2; j <= N; j++, I--)
    {
        for (int i = 1; i <= N; i++)
        {
            int diff = abs(F[j] - F[i]);
            if (diff > maxdiff)
            {
                maxdiff = diff;
                maxidx_i = i;
                maxidx_j = j;
            }
        }
    }
    F[maxidx_i] = F[maxidx_j] = true;
    int maxsum = max(hang_recurse(A, N, N - 1, maxidx_i, F),
                     hang_recurse(A, N, N - 1, maxidx_j, F));
    delete [] F;
    return maxdiff * N + maxsum;
}