c++ - TCS MockVita 2019 第二轮问题 : Hop Game

Question

我正在尝试解决 TCS MockVita 2019 Round 2 中提出的问题:

问题描述

高斯学校的数学老师 Felix Kline 博士介绍了以下游戏来教他的学生解决问题。他将一系列“跳石”(纸片)排成一行，并在每 block 石头上标记点(正数)。

学生从一端开始跳到另一端。一个人可以踩在一 block 石头上并将石头上的数字加到他们的累计分数中，或者跳过一 block 石头并落在下一 block 石头上。在这种情况下，他们得到的分数是他们落地的石头上标记的两倍，但没有得到他们跳过的石头上标记的分数。

在旅程中最多一次，学生可以(如果他们选择的话)进行“双跳”——也就是说，他们连续跳过两 block 石头——他们将获得三倍于他们落地的石头的点数上，但不是他们跳过的石头的点。

老师希望他的学生做一些思考并想出一个计划来获得尽可能高的分数。给定石子序列上的数字，编写一个程序以确定可能的最大分数。

约束

序列中的石子数<30

输入格式

第一行包含N，整数的个数(这是一个正整数)

下一行包含用逗号分隔的 N 个点(每个点都是正整数)。这些是石头上按放置顺序排列的点。

输出

一个整数代表最高分

测试用例

解释

示例 1

输入

3

4,2,3

输出

10

解释

有 3 block 石头(N=3)，点数(按排列顺序)分别为 4,2 和 3。

如果我们踩到第一 block 石头跳过第二 block 得到 4 + 2 x 3 = 10。双跳到第三 block 石头只会得到 9。因此结果是 10，没有使用双跳

示例 2

输入

6

4,5,6,7,4,5

输出

35

解释

N=6，给出点数顺序。获得35的一种方法是先双跳到石头3(3 x 6=18)，转到石头4(7)并跳到石头6 (10分)共35分。二段跳只用了一次，结果是35分。

我发现这是一个动态规划问题，但我不知道我做错了什么，因为我的解决方案无法通过所有测试用例。我的代码通过了我创建的所有测试。

unordered_map<int, int> lookup;
int res(int *arr, int n, int i){

    if(i == n-1){
        return 0;
    }

    if(i == n-2){
        return arr[i+1];
    }

    if(lookup.find(i) != lookup.end())
        return lookup[i];

    int maxScore = 0;

    if(i< n-3 && flag == false){
        flag = true;
        maxScore = max(maxScore, 3 * (arr[i+3]) + res(arr, n, i+3));
        flag = false;
    }
    maxScore = max(maxScore, (arr[i+1] + res(arr,n,i+1)));

    lookup[i] = max(maxScore, 2 * (arr[i+2]) + res(arr, n, i+2));

    return lookup[i];
}

cout << res(arr, n, 0) + arr[0];  // It is inside the main()

我希望您能找到我代码中的错误并给出正确的解决方案，以及任何未通过该解决方案的测试用例。谢谢:)

Answer 1

您不需要任何 map 。您需要记住的只是最后几个最大值。每一步你都有两个选择(除了前两个)，以二段跳结束或不二段跳结束。如果你不想做 dj 那么你最好的乐趣是最后一个石头的最大值 + 当前和最后一个之前的石头 + 2 * 当前 max(no_dj[2] + arr[i], no_dj[1] + 2 * arr[i])。

另一方面，如果你想做 dj 而不是你有三个选择，要么在之前的 dj dj[2] + arr[i] 之后跳过一 block 石头，要么跳过最后一 block 石头在一些 dj dj[1] + 2 * arr[i] 或在当前移动中进行双跳之后 no_dj[0] + 3 * arr[i]。

int res(int *arr, int n){
    int no_dj[3]{ 0, 0, arr[0]};
    int dj[3]{ 0, 0, 0};

    for(int i = 1; i < n; i++){
        int best_nodj = max(no_dj[1] + 2 * arr[i], no_dj[2] + arr[i]);
        int best_dj = 0;
        if(i > 1) best_dj = max(max(dj[1] + 2 * arr[i], dj[2] + arr[i]), no_dj[0] + 3 * arr[i]);

        no_dj[0] = no_dj[1];
        no_dj[1] = no_dj[2];
        no_dj[2] = best_nodj;
        dj[0] = dj[1];
        dj[1] = dj[2];
        dj[2] = best_dj;
    }
    return max(no_dj[2], dj[2]);
}

您只需记住两个包含三个元素的数组。双跳后的最后三个最大值和没有双跳的最后三个最大值。