首页 > 试题广场 >

变向

[编程题]变向

热度指数：1783 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛准备在一个3行n列的跑道上跑步。一开始牛牛可以自己选择位于(1,1)还是(2,1)还是(3,1)。

跑道的每一格都有一些金币，当牛牛跑到一个格子，他会获得这个格子的所有金币。

当牛牛位于第i行第j列时，他可以的下一步最多可能有三种选择：

1. 不花费金币跑到第i行第j+1列
2. 花费 $m_j$ 的金币跑到第i-1行第j+1列（如果i=1则不可以这么跑）。
3. 花费 $m_j$ 的金币跑到第i+1行第j+1列（如果i=3则不可以这么跑）。
（牛牛是一个富豪，本身带了很多的金币，所以你不用担心他钱不够用）

现在告诉你所有格子的金币数量和每一列的金币花费，牛牛想知道他跑到第n列最多可以赚得多少金币（赚得金币=获得金币-消耗金币）

示例1

输入

3,[1,9,3],[6,4,6],[1,1,5],[3,2,1]

输出

说明

一开始牛牛选择位于第2行第1列，拿到6个金币。然后牛牛花3金币到第1行的2列拿到9个金币，最后牛牛花费2金币到第2行第3列。总共获得21金币，消耗5金币。赚得16金币。

备注:


第1个参数n代表跑道的列数
第2，3，4个参数vector<int> a1,a2,a3各有n个元素，代表第1，2，3行每一列的金币个数
第5个参数vector<int> m有n个元素代表每一列进行换行的时候需要的金币花费

算法知识视频讲解

钢琴手1720

dp[i][j]表示当牛牛当前站在(i,j)上的最大收益；

以dp[0][j]为例，当牛牛站在(0,j)上时，他可能是从(0,j-1)过来的，也有可能是从(1,j-1)上花了m[j-1]的转向费过来的，取max(dp[0][j-1],dp[1][j-1]-m[j-1]),当然，不要忘了a1[j]上的收入，就是dp[0][j]了

class Solution {
public:
    int solve(int n, vector<int>& a1, vector<int>& a2, vector<int>& a3, vector<int>& m) {
        // write code here
        vector<vector<int> > dp(3,vector<int>(n,0)); //3行n列矩阵
        //初始化
        dp[0][0]=a1[0];
        dp[1][0]=a2[0];
        dp[2][0]=a3[0];
        for(int i=1;i<n;i++){
            dp[0][i]=max(dp[0][i-1],dp[1][i-1]-m[i-1])+a1[i];
            dp[1][i]=max(dp[1][i-1],max(dp[0][i-1],dp[2][i-1])-m[i-1])+a2[i];
            dp[2][i]=max(dp[2][i-1],dp[1][i-1]-m[i-1])+a3[i];
        }
        int Max = max(dp[0][n-1],max(dp[1][n-1],dp[2][n-1]));
        return Max;
    }
};

发表于 2020-07-24 14:05:57 回复(0)

C/C++

nbgao

class Solution {
public:
    int solve(int n, vector<int>& a1, vector<int>& a2, vector<int>& a3, vector<int>& m) {
        int x=a1[0], y=a2[0], z=a3[0], xx, yy, zz;
        for(int i=0;i<n-1;i++){
            xx = max(x, y-m[i]) + a1[i+1];
            yy = max(y, max(x, z)-m[i]) + a2[i+1];
            zz = max(z, y-m[i]) + a3[i+1];
            x = xx; y = yy; z = zz;
        }
        return max(x, max(y, z));
    }
};

编辑于 2020-06-20 01:05:57 回复(0)

Python

牛客465901099号

动态规划python总是运行超时，想问一问有没有复杂度更小的方法啊

class Solution:

def solve(self , n , a1 , a2 , a3 , m ):
# write code here
dp = [[0 for i in range(3)] for j in range(n)]
dp[0][0]=a1[0]
dp[0][1]=a2[0]
dp[0][2]=a3[0]
for i in range(1,n):
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]- m[i - 1])+a1[i]
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] - m[i - 1])+a3[i]
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - m[i-1], dp[i - 1][2] - m[i - 1]) +a2[i]
return max(dp[n - 1][0], dp[n - 1][1], dp[n - 1][2])

发表于 2020-06-09 20:01:33 回复(2)

七耀之心

这题有毒。Python3提交好多次都超时，我就想知道排名第一的通过代码是怎么过的，然后复制粘贴一个没改，还是超时

发表于 2020-10-20 20:26:10 回复(0)

Resolmi

题目意思看明白就行了

public int solve (int n, int[] a1, int[] a2, int[] a3, int[] m) {
    // write code here
    int[][] dp = new int[3][n];
    dp[0][0] = a1[0];
    dp[1][0] = a2[0];
    dp[2][0] = a3[0];
    for (int j = 1; j < n; j++) {
        dp[0][j] = a1[j] + Math.max(dp[0][j-1], dp[1][j-1]-m[j-1]);
        dp[1][j] = a2[j] + Math.max(dp[1][j-1], Math.max(dp[0][j-1]-m[j-1], dp[2][j-1]-m[j-1]));
        dp[2][j] = a3[j] + Math.max(dp[2][j-1], dp[1][j-1]-m[j-1]);
    }
    return Math.max(dp[0][n-1],Math.max(dp[1][n-1], dp[2][n-1]));
}

发表于 2020-08-30 22:49:06 回复(0)

一叶呼呼

public int solve (int n, int[] a1, int[] a2, int[] a3, int[] m) {
    //从后往前推，从前往后写。如果走到0,n-1获得最多的金币，那么怎么走到0,n-1呢？ 从0,n-2走,还是从1，n-2走，->求max
    // write code here
    // dp 代表牛牛位于此位置上时的最大金币。
    int[][] dp = new int[3][n];
    dp[0][0] = a1[0];
    dp[1][0] = a2[0];
    dp[2][0] = a3[0];
    for(int i=1;i<n;i++){
        //站到0,i 位置上时有两种情况，一是从第一列向前一步，二是从第二列第i-1个位置上 向左前 走到第一列。
        dp[0][i] = Math.max(dp[0][i-1],dp[1][i-1]-m[i-1]) + a1[i];
        //站到1,i 位置上时有三种情况
        dp[1][i]=Math.max(Math.max(dp[0][i-1],dp[2][i-1])-m[i-1],dp[1][i-1])+a2[i];
        //站到2,i 位置上时有两种种情况
        dp[2][i]=Math.max(dp[2][i-1],dp[1][i-1]-m[i-1])+a3[i];
    }
    return Math.max(Math.max(dp[0][n-1],dp[1][n-1]),dp[2][n-1]);
}

编辑于 2020-08-18 22:00:54 回复(0)

復活の検事

import java.util.*;

public class Solution {
    /**
     * 变相
     * @param n int整型
     * @param a1 int整型一维数组
     * @param a2 int整型一维数组
     * @param a3 int整型一维数组
     * @param m int整型一维数组
     * @return int整型
     */
    public int solve (int n, int[] a1, int[] a2, int[] a3, int[] m) {
        int[][] dp = new int[4][n+1];
        dp[1][1] = a1[0];
        dp[2][1] = a2[0];
        dp[3][1] = a3[0];

        for(int j=2;j<=n;j++){
            dp[1][j] = a1[j-1] + Math.max(dp[1][j-1], dp[2][j-1] - m[j-2]);
            dp[2][j] = a2[j-1] + Math.max(dp[2][j-1], Math.max(dp[1][j-1], dp[3][j-1]) - m[j-2]);
            dp[3][j] = a3[j-1] + Math.max(dp[3][j-1], dp[2][j-1] - m[j-2]);
        }

        return Math.max(dp[1][n], Math.max(dp[2][n], dp[3][n]));
    }
}

发表于 2020-08-10 19:36:25 回复(0)

牛客174867978号

先计算每列最大数的和记为 sum

再计算每行的和 n1,n2,n3

计算总花费的金币数量 hf

如果 sum - hf > n1 or n2 or n3 ,则最大值不小于 sum -hf

如果不成的话就很麻烦我这个也是偷懒的但是比他人的要好些

class Solution:
    def solve(self, n, a1, a2, a3, m):
        # write code here
        a = (a1, a2, a3)
        cd = len(m)
        res_sum = 0

        # 这个是列,找出每一列
        for j in range(0, n):
            mx = []
            # 这个是行,找出每一行中的数
            for i in range(0, 3):
                mx.append(a[i][j])
            # 这个结果是每列最大数的总和
            res_sum += max(mx)

        num1, num2, num3 = 0, 0, 0
        # 计算第一行的总和
        for j in range(0, n):
            mx = []
            mx.append(a[0][j])
            # 这个结果是每列最大数的总和
            num1 += sum(mx)
        # 计算第二行的总和
        for j in range(0, n):
            mx = []
            mx.append(a[1][j])
            # 这个结果是每列最大数的总和
            num2 += sum(mx)
        # 计算第三行的总和
        for j in range(0, n):
            mx = []
            mx.append(a[2][j])
            # 这个结果是每列最大数的总和
            num3 += sum(mx)

        hf = 0
        for i in range(0, cd - 1):
            hf += m[i]

        max1 = res_sum - hf
        min = (num1, num2, num3)
        for i in min:
            if i >= max1:
                max1 = i
        max_z = max1

        return max_z

发表于 2020-07-14 17:46:13 回复(0)

好菜啊

public int solve (int n, int[] a1, int[] a2, int[] a3, int[] m) {
        int[][] dp=new int[3][n];
        dp[0][0]=a1[0];
        dp[1][0]=a2[0];
        dp[2][0]=a3[0];
        for(int i=1;i<n;i++){
            dp[0][i]=Math.max(dp[0][i-1],dp[1][i-1]-m[i-1])+a1[i];
            dp[1][i]=Math.max(Math.max(dp[0][i-1],dp[2][i-1])-m[i-1],dp[1][i-1])+a2[i];
            dp[2][i]=Math.max(dp[2][i-1],dp[1][i-1]-m[i-1])+a3[i];
        }
        return Math.max(Math.max(dp[0][n-1],dp[1][n-1]),dp[2][n-1]);
    }

发表于 2020-04-02 08:10:53 回复(0)