首页 > 试题广场 >

流浪者与宝藏

[编程题]流浪者与宝藏

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

牛牛流浪大陆的时候偶然间发现了一个地图和k把钥匙，地图上标出了一些宝藏的位置。

一把钥匙可以开启一个宝藏，获得该宝藏里面的金币，钥匙使用后会被损坏无法再次使用，一个位置(i,j)可能有多个宝藏，但是一个位置只能使用一把钥匙。

因为牛牛是一个精通传送术的流浪者，所以他一步可以走很远。但是他不会走回头路，也不会在一块地方停留。

换言之，如果牛牛当前位于第i行第j列，那么他下一步的位置的行号的范围是[i+1,inf),列号的范围是[j+1,inf)。inf代表无穷大

牛牛最开始位于位置(0,0)

现在牛牛想知道，他最多可以获得多少金币。

示例1

输入

3,3,[1,2,3],[2,1,2],[3,2,2]

输出

说明

牛牛一共有三把钥匙，他可以开启(1,2)处的宝藏获得3个金币，但是之后无法再走到有金币的位置
他也可以先开启(2,1)处的宝藏获得2个金币，再开启(3,2)处的宝藏获得2个金币，总共获得4个金币。

备注:



第一个参数n代表宝藏的个数
第二个参数k代表钥匙个数
第三个参数x包含n个元素，代表n个宝藏的行号
第四个参数y包含n个元素，代表n个宝藏的列号
第五个参数a包含n个元素，代表n个宝藏内的金币数量。

算法知识视频讲解

C/C++

nbgao

class Solution {
public:
    /**
     * 流浪者与宝藏
     * @param n int整型 
     * @param k int整型 
     * @param x int整型vector 
     * @param y int整型vector 
     * @param a int整型vector 
     * @return int整型
     */
    int solve(int n, int k, vector<int>& x, vector<int>& y, vector<int>& a) {
        int c[501][501], dp1[501][501];
        memset(dp1, 0, sizeof(dp1));
        for(int i=0;i<n;i++)
            c[x[i]][y[i]] = max(c[x[i]][y[i]], a[i]);
        
        for(int t=0;t<k;t++){
            int dp2[501][501];
            memset(dp2, 0, sizeof(dp2));
            for(int i=1;i<=500;i++)
                for(int j=1;j<=500;j++)
                    dp2[i][j] = max(dp1[i-1][j-1]+c[i][j], max(dp2[i-1][j], dp2[i][j-1]));
            memcpy(dp1, dp2, sizeof(dp2));
        }
        return dp1[500][500];
    }
};

发表于 2020-08-30 16:08:31 回复(0)

lil-q

import java.util.*;
 
 
public class Solution {
    /**
     * 流浪者与宝藏
     * @param n int整型
     * @param k int整型
     * @param x int整型一维数组
     * @param y int整型一维数组
     * @param a int整型一维数组
     * @return int整型
     */
    public int solve (int n, int k, int[] x, int[] y, int[] a) {
        // write code here
        int[][] dp = new int[501][501];
        int[][] T = new int [501][501];
        for (int i = 0; i < n; i++)
            T[x[i]][y[i]] = Math.max(a[i], T[x[i]][y[i]]);
         
        for (int m = 1; m < k + 1; m++) {
            int[][] dp2 = new int[501][501];
            for (int i = 1; i < 501; i++) {
                for (int j = 1; j < 501; j++) {
                    dp2[i][j] = Math.max(dp[i - 1][j - 1] + T[i][j], // 最后一步在（i， j)
                        Math.max(dp2[i - 1][j], dp2[i][j - 1])); // 不在（i， j）
                }
            }
            dp = dp2;
        }
        return dp[500][500];
    }
}

发表于 2020-07-29 09:07:17 回复(0)

kiinghom

for(int i = 1; i <= 501; i++){
    for(int j = 1; j <= 501; j++){
        for(int p = 1; p <= k; p++){
            f[i][j][p] = max(f[i][j-1][p], f[i-1][j][p]);
            f[i][j][p] = max(f[i][j][p], f[i-1][j-1][p-1] + mm[i][j]);
        }
    }
}
return f[501][501][k];

f[i][j][p]表示在坐标在[i,j]之内范围内，开p宝箱的最大收益

发表于 2020-04-22 12:20:40 回复(1)