1

我无法解决如何选择元素。

例如，如果我们有 1,2,3,4,5,6,7,8,9,10

我们选择 4,5

那么我们不能选择 6,7,8 但我们可以选择 9th

所以，我想一般来说

如果我们选择 2 个连续元素arr[i] 和 arr[i+1]，

那么我们不能从接下来的 3 个值arr[i+2]、arr[i+3]、arr[i+4]中选择，我们只能从arr[i+5]中选择

例如：

考虑这个有9 个元素的数组

输入：arr[] = {100, 200, 100, 500, 900, 500, 300, 400, 100}

输出：1500

最大金额应为：1500

通过取第 4、5 和 9 位的值获得

即 500+900+100 = 1500

另一个例子：

考虑这个有10 个元素的数组

输入：arr[] = {500, 700, 300, 500, 900, 700, 600, 400, 700, 500}

输出：2800

选择 (2, 5, 9, 10) 处的元素

即 700+900+700+500 = 2800

4

1 回答 1

0

对我来说，这可以通过对动态规划算法的简单修改来完成。实际上，您可以添加一个变量来指示是否选择了最后一个元素。假设您正在考虑位置 idx 的元素，您需要一个变量来告诉您是否选择了 idx - 1：（1）如果不是，您还没有选择任何连续的，您可以继续idx + 1, (2) 如果是，则应从 idx + 4 开始，因为 idx+1, idx+2, idx+3 不再允许被选择。

这是 C++ 中的一个实现：

    const int n = 1000;

    int arr[n];


    int dp[n][2];
    bool mark[n][2];

    int rec(int idx, bool idx_minus1_picked){
        if(idx >= n){
            return 0; // we have reached end of array
        }

        if(mark[idx][lidx_minus1_picked]){
            return dp[idx][idx_minus1_picked];
        }

        int &ret = dp[idx][idx_minus1_picked];
        ret = 0;

        if(idx_minus1_picked){
            //get the maximum between picking or not picking arr[idx]
            ret = max(arr[idx] + rec(idx + 4, false), rec(idx + 1, false));
        }
        else{
            ret = max(arr[idx] + rec(idx + 1, true), rec(idx + 1, false));
        }

        return ret;

    }

int main(){
    int answer = rec(0, false);
    return 0;
}
于 2017-07-28T04:44:15.060 回答