首页 > 试题广场 >

【2021】360编程-火星人的宝藏

[编程题]【2021】360编程-火星人的宝藏

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

X星人发现了一个藏宝图，在藏宝图中标注了N个宝库的位置。这N个宝库连成了一条直线，每个宝库都有若干枚金币。

X星人决定乘坐热气球去收集金币，热气球每次最多只能飞行M千米（假设热气球在飞行过程中并不会发生故障）此外，由于设计上的缺陷，热气球最多只能启动K次。

X星人带着热气球来到了第1个宝库（达到第1个宝库时热气球尚未启动），收集完第1个宝库的金币后将启动热气球前往下一个宝库。如果他决定收集某一个宝库的金币，必须停下热气球，收集完之后再重新启动热气球。当然，X星人每到一个宝库是一定会拿走这个宝库所有金币的。

已知每一个宝库距离第1个宝库的距离（单位：千米）和宝库的金币数量。

请问X星人最多可以收集到多少枚金币？

输入描述:

单组输入。

第1行输入三个正整数N、M和K，分别表示宝库的数量、热气球每次最多能够飞行的距离（千米）和热气球最多可以启动的次数，三个正整数均不超过100，相邻两个正整数之间用空格隔开。

接下来N行每行包含两个整数，分别表示第1个宝库到某一个宝库的距离（千米）和这个宝库的金币枚数。（因为初始位置为第1个宝库，因此第1个宝库所对应行的第1个值为0。）

输入保证所有的宝库按照到第1个宝库的距离从近到远排列，初始位置为第1个宝库。

输出描述:

输出一个正整数，表示最多可以收集的金币数。

示例1

输入

输出

说明

X星人启动热气球两次，分别收集第1个、第3个和第4个宝库的金币，一共可以得到的金币总数为5+8+12=25枚。

算法知识视频讲解

pein531

暴力DP，用dp[i][j]表示到达i宝库时使用j次启动所带来的最大收益。在启动次数固定为times的情况下，dp[i][times]可以由dp[j][times-1]转移而来，状态转移方程为：

dp[i][times] = dp[j][times - 1] + gold[i]

其中j表示离i宝库不超过m公里的宝库，到达i宝库时启动次数为times次，那么到达j宝库时启动次数应该已经使用了times-1次。但是它也可以不从j宝库转移过来，因为从j宝库过来并不一定能使得金币数增加最多，因此j应该是所有能到i宝库的宝库中，能使得金币数增加最多的那个宝库。

动态规划完成后，dp矩阵中的最大值即为X星人最多可以收集到的金币数量。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        int n = Integer.parseInt(params[0]);
        int m = Integer.parseInt(params[1]);
        int k = Integer.parseInt(params[2]);
        int[] pos = new int[n + 1];
        int[] gold = new int[n + 1];
        for(int i = 1; i <= n; i++){
            params = br.readLine().trim().split(" ");
            pos[i] = Integer.parseInt(params[0]);
            gold[i] = Integer.parseInt(params[1]);
        }
        int[][] dp = new int[n + 1][k + 1];
        for(int i = 0; i <= n; i++)
            Arrays.fill(dp[i], Integer.MIN_VALUE);
        dp[1][0] = gold[1];
        int max = 0;
        for(int times = 1; times <= k; times ++){
            for(int i = 2; i <= n; i++){
                for(int j = 1; j < i; j++){
                    if(pos[i] - pos[j] <= m){
                        dp[i][times] = Math.max(dp[i][times], dp[j][times - 1] + gold[i]);
                        max = Math.max(max, dp[i][times]);
                    }
                }
            }
        }
        System.out.println(max);
    }
}

编辑于 2021-08-23 16:41:09 回复(0)

小有不会写程序

//一样的代码，Go只能过两个
func main() {
	var N, M, K int
	fmt.Scanln(&N, &M, &K)
	pos, gold := make([]int, N+1), make([]int, N+1)
	for i := 1; i <= N; i++ {
		fmt.Scanln(&pos[i], &gold[i])
	}

	dp := make([][]int, N+1) //i第几个宝箱，j是第几次启动到i处，时候的，最多金币数
	for i := range dp {
		dp[i] = make([]int, K+1)
		for j := 0; j < K+1; j++ {
			dp[i][j] = math.MinInt32
		}
	}
	dp[1][0] = gold[1]
	var res int

	for times := 1; times <= K; times++ {
		for i := 2; i < N; i++ {
			for j := 1; j < i; j++ {
				if pos[i]-pos[j] <= M {
					dp[i][times] = max(dp[i][times], dp[j][times-1]+gold[i])
					res = max(res, dp[i][times])
				}
			}
		}
	}

	fmt.Printf("%d", res)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

发表于 2022-09-02 21:57:42 回复(0)

好难取个名字

import java.io.*;
import java.util.*;
public class Main{

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = " ";
        while((str = br.readLine()) != null){
            String[] str_array = str.split(" ");
            int n = Integer.parseInt(str_array[0]);
            int m = Integer.parseInt(str_array[1]);
            int k = Integer.parseInt(str_array[2]);
            int[] pre = new int[n+1];
            int[] v = new int[n+1];
            for(int i = 1; i <= n; ++i){
                str_array = br.readLine().split(" ");
                pre[i] = Integer.parseInt(str_array[0]);
                v[i] = Integer.parseInt(str_array[1]);
            }
            int[][] dp = new int[n+1][k+2];
            for(int i = 1; i <= k+1; ++i) dp[1][i] = v[1];
            int result = v[1];
            for(int i = 2; i <= n; ++i){
                for(int j = 2; j <= k+1; ++j){
                    int max = 0;
                    for(int p = 1; p < i; ++p){
                        if(pre[i] - pre[p] <= m) max = Math.max(max,dp[p][j-1]+v[i]);
                    }
                    dp[i][j] = max == v[i]? 0 : max;
                    result = Math.max(result,dp[i][j]);
                }
            }
            System.out.println(result);
        }
    }
}

发表于 2022-09-02 15:30:23 回复(0)

穿着背带裤的鸡哥在唱跳Rap

def solve(nums,n,m,k):
    # dp[i][j] 表示第i次走到j能够获得的最大金币
    dp = [[0]*n for _ in range(k+1)] # (k+1,n)
    dp[0][0] = nums[0][1]
    # print("第一次", dp[0])
    for i in range(1, k+1):
        # 终点
        for e in range(n):
            # 起点
            dp[i][e] = dp[i-1][e]
            for s in  range(e):
                if not dp[i-1][s]&nbs***bsp;nums[s][0]+m < nums[e][0]:
                    continue
                dp[i][e] = max(dp[i][e], dp[i-1][s] + nums[e][1])
        # print(f"第{i+1}次, {dp[i]}")
    return max(dp[k])
 
def main():
    line = list(map(int, input().strip().split()))
    n,m,k = line
    nums = []
 
    for i in range(n):
        nums.append(list(map(int, input().strip().split())))
     
    ans = solve(nums, n, m, k)
    print(ans)
     
main()

最大子序列和

发表于 2022-08-26 15:44:50 回复(0)

菲尼克斯弗兰克

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt(), m = in.nextInt(), k = in.nextInt();
            int[][] arr = new int[n][2];
            for (int i = 0; i < n; i++) {
                arr[i][0] = in.nextInt();
                arr[i][1] = in.nextInt();
            }
            sum = arr[0][1];
            back(arr, n, m, k, 1, 0); // 从0出发从1开始计算
            System.out.println(max);
        }
    }
    // 回溯爆搜它！
    static int sum = 0, max = 0;
    public static void back(int[][] arr, int n, int m, int k, int idx, int pos) {
        if (k == 0 || idx == n) { // 回溯退出
            max = Math.max(max, sum);
            return;
        }
        for (int i = idx; i < n; i++) {
            if (arr[i][0] - pos <= m) { // 当前可以到达
                sum += arr[i][1];
                k--;
                back(arr, n, m, k, i+1, arr[i][0]);
                sum -= arr[i][1];
                k++;
            } else return; // 后面的都不可到达-剪枝
        }
    }
}

发表于 2022-06-13 17:19:57 回复(0)

Ghower

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
         int m = in.nextInt();
        int k = in.nextInt();
        int[][] arr = new int[n][2];
        int i=0;
        while(i<n && in.hasNext()){
            arr[i][0] = in.nextInt();
            arr[i][1] = in.nextInt();
            i++;
        }
        System.out.println(dp(n, m, k, arr, 0));
    }

    private static int dp(int n, int m, int k, int[][] arr, int i) {
        if(k<0) return 0;
        int max = 0;
        for(int j = i+1;j<n && arr[j][0] <= arr[i][0] + m;j++)
            max = Math.max(max,dp(n, m, k - 1, arr, j));
        return arr[i][1] + max;
    }
}

dp函数搞定

编辑于 2022-03-19 20:21:15 回复(0)

送你一朵小红花啊

最短路

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e3+5;
int n,m,ans,k,d=1,dis[N][N];
struct node{
	int num,dep;
};
struct NODE{
	int d,val;
}p[N];
queue<node>que;
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++){
    	scanf("%d%d",&p[i].d,&p[i].val);
	}
	que.push({1,0});
	ans=dis[1][0]=p[1].val;
	while(!que.empty()){
		node x=que.front();
		que.pop();
		int nex=x.num+1;
		while(nex<=n&&x.dep<k&&p[nex].d-p[x.num].d<=m){
			d=x.dep+1;
			dis[nex][d]=max(dis[nex][d],dis[x.num][d-1]+p[nex].val);
			ans=max(ans,dis[nex][d]);
			que.push({nex,d});
			nex++;
		}
	}
	printf("%d",ans);
	return 0;
}

发表于 2022-03-05 14:02:09 回复(0)

寒冰-侠客

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,m,k,a[105],b[105],dp[105][105],ans;
int main()
{
    int i,j;
    cin>>n>>m>>k;
    for(i=1;i<=n;i++)
        cin>>a[i]>>b[i];
    ans=dp[1][0]=b[1];
    for(j=1;j<=k;j++)
    {   /**< 本题可以暴力dp，不过当n很大时可以用单调队列来优化，这也是一种常见的优化方法 */
        deque<int> dq;
        dq.push_back(j);/**< 使用单调队列注意存储的是数组下标 */
        for(i=j+1;i<=n;i++)
        {
            while(dq.size()&&(dp[dq.front()][j-1]==0||a[i]-a[dq.front()]>m))
                dq.pop_front();
            if(dq.size())
                dp[i][j]=dp[dq.front()][j-1]+b[i];
            while(dq.size()&&dp[dq.back()][j-1]<=dp[i][j-1])
                dq.pop_back();
            dq.push_back(i);
            ans=max(ans,dp[i][j]);
        }
    }
    cout<<ans;
    return 0;
}

发表于 2021-08-14 11:52:04 回复(0)

皮蛋秀柚秋

#include<bits/stdc++.h>

using namespace std;
int main(){
    int n,m,p;
    cin>>n>>m>>p;
    //最长上升子序列模型
    //dp[i][j]表示以i城市结尾 并使用j次热气球的最大收益
    vector<vector<int>>dp(n+1,vector<int>(p+1,INT_MIN));
    int a[n+1],b[n+1];
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
    dp[1][0]=b[1];
    
    int ans = 0;
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++)
            //从j城市能到达i城市
               if(a[i]-a[j]<=m){
                   for(int k=1;k<=p;k++){
                       //取所有能跳转过来的城市j中的最大值
                       dp[i][k]=max(dp[i][k],dp[j][k-1]+b[i]);
                       
                       //记录最大值
                       ans = max(ans,dp[i][k]);
                   }
                            
               }
                     
    }
    cout<<ans<<endl;
    return 0;
}

发表于 2021-06-07 11:07:43 回复(0)

牛客12312341

最长子序列和模型

我们增加一个维度表示用了k次热气球即可

#include<bits/stdc++.h>

using namespace std;

const int N=110;
int f[N][N];
int a[N],b[N];

int main(){
    ios::sync_with_stdio(false);
    int n,m,p;
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
    memset(f,-0x3f,sizeof(f));
    f[1][0]=b[1];
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++)
               if(a[i]-a[j]<=m) 
                     for(int k=1;k<=p;k++)
                            f[i][k]=max(f[i][k],f[j][k-1]+b[i]);
    }
    int ans=0;//枚举最后的结果，有可能热气器次数没用完就取完了所有金币
    for(int i=1;i<=n;i++)
        for(int j=1;j<=p;j++)
            ans=max(ans,f[i][j]);
    cout<<ans<<endl;
    return 0;
}

编辑于 2021-05-11 02:25:51 回复(0)

Sensuki

package ghc;

import java.util.ArrayList;
import java.util.Scanner;

public class Main{
public static void main(String[] args){
        String init = new Scanner(System.in).nextLine();
String[] initstr=init.split(" ");
     int N = Integer.parseInt(initstr[0]);
     int K= Integer.parseInt(initstr[1]);
     int M = Integer.parseInt(initstr[2]);
ArrayList<Number> distance = new ArrayList<>();
ArrayList<Number> money = new ArrayList<>();
for(int p=0;p<N;p++) {
    @SuppressWarnings("resource")
            String str = new Scanner(System.in).nextLine();
    String[] srr=str.split(" ");
    distance.add(Integer.valueOf(srr[0]));
    money.add(Integer.valueOf(srr[1]));
}

System.out.print(findPlace(distance,money,K,M));

}

public static int findPlace(ArrayList<Number> distance,ArrayList<Number> money,int K,int M) {
    int finalCoin=(int) money.get(0);
    money.remove(0);
    money.add(0,0);//拿走第一个点金币
     int nowPoint=0;//当前点
    for(int m=0;m<M;m++) {
        int tmp=0;//目标点金币
        int location=0;//目标点
        //遍历所有距离内的点，找金币最多的点
    for(int p=0;p<distance.size();p++) {
        if( (int)distance.get(p)-(int)distance.get(nowPoint)<=K && (int)money.get(p) != 0) {
            if(tmp < (int)money.get(p)) {
                tmp = (int)money.get(p);
                location = p;
            }
        }
    }
    finalCoin += (int)money.get(location);
    nowPoint = location;
    //System.out.print("第"+(m+1)+"次,拿到金币"+money.get(location)+"\n");
    money.remove(nowPoint);
    money.add(nowPoint,0);//拿走金币
    //System.out.print("当前点为"+nowPoint+",当前点金币为"+money.get(nowPoint)+"\n");
    }
    return finalCoin;
}
}

编辑于 2021-05-08 17:05:52 回复(0)

Java

电子柯基犬

package test4;

import java.util.Scanner;

/**
 * @author xq
 * @create 2021-05-07-21:10
 */
public class Main{
//    public static void main(String[] args) {
//        long sum = 0;
//        Scanner scanner = new Scanner(System.in);
//        while (scanner.hasNext()){
//            int nextInt = scanner.nextInt();
//            int[] ints = new int[nextInt];
//            for (int i = 0; i < nextInt; i++) {
//                ints[i] = scanner.nextInt();
//                sum+=ints[i];
//            }
//            for (int i = 0; i < nextInt; i++) {
//                for (int j = i+1; j < nextInt; j++) {
//                    int temp = ints[i]|ints[j];
//                    sum+=temp;
//                }
//            }
//        }
//        System.out.println(sum);
//    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        int K = scanner.nextInt();
        int[][] ints = new int[N][2];
        int sum = 0;
        for (int i = 0; i < N; i++) {
            ints[i][0] = scanner.nextInt();
            ints[i][1] = scanner.nextInt();
            sum+=ints[i][1];
        }
        if (K>=N){
            System.out.println(sum);
            System.exit(0);
        }
        int[][] dp = new int[N][K+1];
        dp[0][0] = ints[0][1];
        int max = 0;
        for (int i = 1; i <= K; i++) {
            for (int j = 0; j < N; j++) {
                if (dp[j][i-1]>0){
                    for (int k = j+1; k < N; k++) {
                        if (ints[k][0]-ints[j][0]<=M){
                            dp[k][i] = Math.max(dp[k][i],dp[j][i-1]+ints[k][1]);
                            max = Math.max(dp[k][i],max);
                        }
                    }
                }
            }
        }
        System.out.println(max);
    }
}

发表于 2021-05-08 09:30:19 回复(0)