首页 > 试题广场 >

【2021】360编程题-神枪手

[编程题]【2021】360编程题-神枪手
  • 热度指数:1143 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

小马最近找到了一款打气球的游戏。

每一回合都会有 n个气球,每个气球都有对应的分值,第 i个气球的分值为ai

这一回合内,会给小马两发子弹,但是由于小马的枪法不准,一发子弹最多只能打破一个气球,甚至小马可能一个气球都打不中。

现给出小马的得分规则:

1. 若小马一只气球都没打中,记小马得0分。

2. 若小马打中了第 i只气球,记小马得ai 分。

3. 若小马打中了第 i只气球和第 j只气球(i<j),记小马得 ai|aj分。

(其中| 代表按位或,按位或的规则如下:

参加运算的两个数,按二进制位进行或运算,只要两个数中的一个为1,结果就为1。
即 0|0=0, 1|0=1, 0|1=1, 1|1=1。
例 2|4即 00000010|00000100=00000110,所以2|4=6

现在请你计算所有情况下小马的得分之和。


输入描述:

第一行,一个整数n,表示此回合的气球数量。

第二行,用空格分开的n 个整数,第i个整数为ai,表示每个气球对应的分值。

对于其中60% 的数据, 1≤n≤1000, 1≤ai≤100000

对于另外 40% 的数据,  1≤n≤50000, 1≤ai≤100000



输出描述:

一行一个整数,代表所有情况下小马的得分之和。

示例1

输入

3 
1 2 3

输出

15

说明

package test4;

import java.util.Scanner;

/**
 * @author xq
 * @create 2021-05-07-21:10
 */
public class Main{
    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);
    }
//    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);
//    }
}

发表于 2021-05-08 09:44:45 回复(0)