首页 > 试题广场 >

勇敢的妞妞

[编程题]勇敢的妞妞

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

美丽的牛家庄受到了外星人的侵略, 勇敢的妞妞要上战场抵御侵略。

在妞妞上战场前, 村长牛牛给了妞妞N件装备, 妞妞需要选择其中的K件,装备在身上提升自己的战斗力。每件装备有5种属性增幅值,对于第i件装备它的属性增幅值为(r_i1, r_i2, r_i3, r_i4, r_i5), 分别代表该装备对不同的属性值增幅。

当妞妞装备多件装备的时候,由于装备之前会互相影响, 对于每种属性值的增幅并不是所有装备该属性值之和, 而是该种属性值下所有装备中最大的属性值。而妞妞最终增加的战斗力为这5种属性值增幅之和。

妞妞一定要保卫牛家庄, 所以她希望她能提升尽可能多的战斗力, 请你帮帮她计算她最多能增加多少战斗力。

输入描述:

输入包括N+1行,
第一行包括两个正整数N和K(1 <= N <= 10000, 1 <= K <= N), 分别表示一共有的装备数量和妞妞需要选择的装备数量。
接下来的N行,每行5个整数r_i1, r_i2, r_i3, r_i4, r_i5(0 <= r_i1, r_i2, r_i3, r_i4, r_i5 <= 10000)表示第i件装备的5种属性值增幅。

输出描述:

输出一个整数,表示妞妞最多能增加的战斗力。

示例1

输入

4 2
30 30 30 30 0
50 0 0 0 0
0 50 0 50 10
0 0 50 0 20

输出

说明

妞妞要从4件装备中选取2件, 如果妞妞选择第1件和第3件装备,那么增加的战斗力为30 + 50 + 30 + 50 + 10 = 170, 这是最大的方案。

算法知识视频讲解

Reyzal

本套试题AC代码在https://github.com/ReyzalX/nowcoder查看。
如果暴力，情况太复杂了。
预处理数据：

选当前装备第1条属性，可以得到的最大值，当前装备第2条属性可以得到的最大值...
取当前装备第1和第2条属性，可以得到的最大值，第1和第3属性可以得到的最大值。
......最后遍历这个预处理后的数据即可。

#include<bits/stdc++.h>

using namespace std;
int result = 0;
int n, K;
int best[32] = { 0 };

void dfs(int cur,int flag,int sum) {
    if (cur == K)
    {
        result = max(result,sum);
        return;
    }
    for (int i = 0; i < 32; i++)
    {
        if (i & flag)
            continue;
        dfs(cur + 1, i | flag, sum + best[i]);
    }
}
int main()
{
    cin >> n >> K;
    vector<vector<int>> data(n, vector<int>(5));
    int maxv[5] = { 0 };
    for (int i = 0; i < n; i++)
    {
        cin >> data[i][0] >> data[i][1] >> data[i][2] >> data[i][3] >> data[i][4];
        for (int k = 0; k < 5; k++)
        {
            maxv[k] = max(maxv[k], data[i][k]);
        }
        //这里是计算当使用当前装备第12345个属性时，加成是多少
        //best记录最大加成
        //11111 表示使用装备5个属性
        //11110 使用装备第1234属性 11101 使用装备第1235属性 类推
        for (int j = 1; j < 32; j++)
        {
            int temp = 0;
            for (int k = 0; k < 5; k++)
            {
                if (j&(1 << k)) {
                    temp += data[i][k];
                }
            }
            best[j] = max(best[j], temp);
        }
    }
    if (K >= 5)
    {
        //大于5肯定单属性最高的
        for (int i = 0; i < 5; i++)
        {
            result += maxv[i];
        }
    }
    else {
        //小于5
        //选单件5个属性的
        //选单件4个属性的，下一件是1个属性
        //选单件3个属性的，下一件可以2个属性或者1个属性
        //...可以动态规划，小规模直接dfs就行了
        dfs(0, 0,0);
    }
    cout << result << endl;
    return 0;
}

发表于 2018-03-26 01:04:52 回复(0)

ZVINK

状压dp 可过，第一维应该可以不要

#include<cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 10010;

int N;
int K;
int a[maxn][5];
int A[maxn][32];
int dp[maxn][32][5];
int MAX[5];

int main()
{
    scanf("%d%d",&N,&K);
    for(int i = 0;i<N;++i)
    {
        for(int j = 0;j<5;++j)
        {
            scanf("%d",&a[i][j]);
        }
    }
    if( K >=5)
    {
        memset(MAX,0,sizeof MAX);
        for(int i = 0;i<N;++i)
        {
            for(int j = 0;j<5;++j)
            {
                MAX[j] = max(MAX[j],a[i][j]);
            }
        }
        int ans = 0;
        for(int i = 0;i<5;++i)
            ans+= MAX[i];
        printf("%d\n",ans);
        return 0;
    }
    memset(A,0,sizeof A);
    memset(dp,0,sizeof dp);
    for(int i =  0;i<N;++i)
    {
        for(int j = 0;j<32;++j)
        {
            for(int k = 0;k<5;++k)
            {
                if((j & (1<<k) ) > 0)
                    A[i][j]+=a[i][k];
            }
            //printf("A[%d][%d]=%d\n",i,j,A[i][j]);
        }
    }
    for(int i = 0;i<N;++i)
    {
        for(int k = 1;k<=4;++k)
        for(int j = 0;j<32;++j)
        {
                dp[i][j][k] = dp[i-1][j][k];
                for(int n = 0;n<=j;++n) if((n&j) >0 &&(n&j) == n)
                {
                    //printf("i:%d j:%d n:%d j-n:%d\n",i,j,n,j-n);
                    //dp[i][j][k] = std::max(dp[i-1][j][k],dp[i-1][j-n][k-1]+A[i][n]);
                    if(dp[i-1][j-n][k-1] + A[i][n] > dp[i][j][k])
                        dp[i][j][k] = dp[i-1][j-n][k-1] +A[i][n];
                    //printf("dp[%d][%d][%d] = %d\n",i-1,j-n,k-1,dp[i-1][j-n][k-1]);
                  //  printf("A[%d][%d] = %d\n",i,n,A[i][n]);
                }
                //printf("------dp[%d][%d][%d] = %d\n",i,j,k,dp[i][j][k]);
        }
    }
    printf("%d\n",dp[N-1][31][K]);
    return 0;
}

发表于 2018-03-15 16:33:16 回复(4)

C/C++

霍七

本套6道题全部pass的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)

牛客网上的其他题目解答也在持续更新。

【题解】没有想到好办法，m大于等于5时取各个属性的最大值，m小于等于3时遍历，m等于4时为防止超时，用一点小小的技巧即可通过。

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int n, m; cin >> n >> m;
    int **r = new int*[n], result = 0;
    int maxr[5] = { 0 };
    for (int i = 0; i < n; i++) {
        r[i] = new int[5];
        for (int j = 0; j < 5; j++) {
            cin >> r[i][j];
            maxr[j] = max(maxr[j], r[i][j]);
        }
    }
    if (m == 1) {
        for (int i = 0; i < n; i++) {
            int temp = 0;
            for (int k = 0; k < 5; k++) {
                temp += r[i][k];
            }
            result = max(result, temp);
        }
    }
    else if (m == 2) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int temp = 0;
                for (int k = 0; k < 5; k++) {
                    temp += max(r[i][k], r[j][k]);
                }
                result = max(result, temp);
            }
        }
    }
    else if (m == 3) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int p = 0; p < n; p++) {
                    int temp = 0;
                    for (int k = 0; k < 5; k++) {
                        temp += max(max(r[i][k], r[j][k]), r[p][k]);
                    }
                    result = max(result, temp);
                }
            }
        }
    }
    else if (m == 4) {
        int maxtemp[5][5] = { 0 };
        for (int p = 0; p < 5; p++) {
            for (int q = p + 1; q < 5; q++) {
                int temp = 0;
                for (int i = 0; i < n; i++) {
                    temp = max(temp, r[i][p] + r[i][q]);
                }
                for (int k = 0; k < 5; k++) {
                    if (k != p && k != q) {
                        temp += maxr[k];
                    }
                }
                result = max(result, temp);
            }
        }
    }
    else {
        for (int k = 0; k < 5; k++) {
            result += maxr[k];
        }
    }
    cout << result;
    return 0;
}

编辑于 2017-12-26 14:43:10 回复(1)

逗比请来的猴子

import java.util.Scanner;

/*
 * 参考大神的解题思路：https://www.nowcoder.com/questionTerminal/aaad2e0e1dc74d5da4587ad7f6e0de8d
 * 主要是k=4的情况的特殊处理，其他的很好理解。
 * K>=5时，可以任取最大值即可；
 * k<=3，直接暴力求解；
 * k=4，可以选择到3个最大的col，然后对于剩余的2个col遍历比较，具体参见实现代码
 * */
public class SimpleDevice {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int N = scanner.nextInt();
            int K = scanner.nextInt();
            int[][] devices = new int[N][5];
            int[] maxCols = new int[5];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < 5; j++) {
                    devices[i][j] = scanner.nextInt();
                    maxCols[j] = Math.max(maxCols[j], devices[i][j]);
                }
            }
            int tmp = 0;
            if (K >= 5) {
                for (int i = 0; i < 5; i++) {
                    tmp += maxCols[i];
                }
                System.out.println(tmp);
            } else {
                if (K == 1) {
                    for (int i = 0; i < N; i++) {
                        int tmpSum = 0;
                        for (int j = 0; j < 5; j++) {
                            tmpSum += devices[i][j];
                        }
                        tmp = Math.max(tmp, tmpSum);
                    }
                } else if (K == 2) {
                    for (int i = 0; i < N - 1; i++) {
                        for (int j = i + 1; j < N; j++) {
                            int tmpSum = 0;
                            for (int k = 0; k < 5; k++) {
                                tmpSum += Math.max(devices[i][k], devices[j][k]);
                            }
                            tmp = Math.max(tmp, tmpSum);
                        }
                    }
                } else if (K == 3) {
                    for (int i = 0; i < N - 2; i++) {
                        for (int j = i + 1; j < N - 1; j++) {
                            for (int k = j + 1; k < N; k++) {
                                int tmpSum = 0;
                                for (int l = 0; l < 5; l++) {
                                    tmpSum += Math.max(devices[i][l], Math.max(devices[j][l], devices[k][l]));
                                }
                                tmp = Math.max(tmp, tmpSum);
                            }
                        }
                    }
                } else {
//                    如果直接暴力求解的话，会超时
                    for (int i = 0; i < 5; i++) {
                        for (int j = i + 1; j < 5; j++) {
                            int maxTwoCol = 0;
//                            挑选任意两个cols和的最大值
                            for (int k = 0; k < N; k++) {
                                maxTwoCol = Math.max(maxTwoCol, devices[k][i] + devices[k][j]);
                            }
                            int tmpSum = maxTwoCol;
//                            从最大的cols中取出剩余的三个col
                            for (int k = 0; k < 5; k++) {
                                if (k != i && k != j) {
                                    tmpSum += maxCols[k];
                                }
                            }
//                            比较更新
                            tmp = Math.max(tmp, tmpSum);
                        }
                    }

                }
                System.out.println(tmp);
            }
        }
    }
}

发表于 2018-03-27 16:02:11 回复(0)