首页 > 试题广场 >

取数游戏

[编程题]取数游戏

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

给定两个长度为 n 的整数列 A 和 B ，每次你可以从 A 数列的左端或右端取走一个数。假设第 i 次取走的数为 $A_x \$ ，则第i次取走的数的价值 $v_i = b_i \times a_x \$ ，现在希望你求出 $\sum_{i=1}^n v_i \$ 的最大值。

数据范围： $1 \le n \le 1000 \$ , $1 \le A_i,B_i \le 1000 \$

示例1

输入

[1,1000],[2,1]

输出

示例2

输入

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

输出

说明

第一次从左边取走a1，v1=a1⋅b1=1,
第二次从左边取走a2，v2=a2⋅b2=6,
第三次从右边取走a5，v3=a5⋅b3=12,
第四次从右边取走a4，v4=a4⋅b4=8,
第五次取走剩下的a3，v5=a3⋅b5=25。
总价值∑vi=1+6+12+8+25=52

算法知识视频讲解

C++

宇宙无敌黑起

dp[i][j]表示区间i到j可以取到的最大值
dp[i][j]=max(dp[i+1][j]+A[i]*B[n-(j-i)],dp[i][j-1]+A[j]*B[n-(j-i)])

class Solution {

public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A int整型vector
* @param B int整型vector
* @return int整型
*/
int numbergame(vector<int>& A, vector<int>& B) {
// write code here
int n = A.size();
vector<vector<int> > dp(n, vector<int>(n));
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
int l = j - i + 1;
if (i == j) {
dp[i][j] = A[i] * B[n - 1];
} else {
dp[i][j] = max(dp[i + 1][j] + A[i] * B[n - l], dp[i][j - 1] + A[j] * B[n - l]);
}
}
}
return dp[0][n - 1];
}
};

发表于 2022-05-04 19:09:08 回复(0)

_王泥煤

    public int numbergame (ArrayList<Integer> A, ArrayList<Integer> B) {
        // write code here
        int[] a = A.stream().mapToInt(Integer::valueOf).toArray();
        int[] b = B.stream().mapToInt(Integer::valueOf).toArray();
        // dp[i][j]: 左边已经取走了i个数，右边取走了若干个数，总共已经取走了j个数，此时能获得的最高得分
        // dp[i][j] = (取左边)dp[i+1][j+1] + a[i]*b[j], (取右边)dp[i][j+1] + a[]*b[j]
        int[][] dp = new int[a.length][b.length];
        for(int i = 0; i < a.length; ++i) {
            dp[i][b.length-1] = a[i] * b[b.length-1];
        }
        for(int i = a.length-2; i >= 0; --i) {
            for(int j = b.length-2; j >= i; --j) {
                dp[i][j] = Math.max(dp[i+1][j+1] + a[i]*b[j], dp[i][j+1] + a[a.length-j+i-1]*b[j]);
            }
        }
        return dp[0][0];
    }

发表于 2022-03-04 11:25:59 回复(0)