列表

详情

NC219676. 来自良心出题人wzc的简单题

描述

罗德岛训练室今天的使用人是干员w，她的任务是使用手上的三个遥控炸弹，尽可能摧毁最大价值的目标。

测试区域是一个n*n的矩阵，w可以选择任意格子安放炸弹，如果选择了位置[i][j]安放炸弹，那么对于所有的[i][k]满足|k-j|<=2和所有[l][j]满足|l-i|<=2的点，都会被这个炸弹所摧毁。也就是说炸弹安放位置以及其上下左右各向外延伸2个单位长度的格子都会被其摧毁，重复被摧毁的格子只计算一次该格子的价值。
（如下图所示，如果在该5*5矩阵的中心位置安放炸弹，除了安放的位置外，四个方向上8个画X的位置也会被摧毁）

睿智的勃士总是能帮助w快速计算出可以摧毁的最大价值。

输入描述

第一行为一个整数n，代表矩阵的宽度。(1<=n<=10)
接下来第1+i行(1<=i<=n)，每行为空格隔开的n个整数a[i][j]。代表矩阵位置[i][j]的价值是多少。(0<=a[i][j]<=1e9)

输出描述

输出一个整数，代表能摧毁的最大价值。

示例1

输入: 

5
2 2 2 2 2
2 0 2 0 2
2 2 2 2 2
2 0 2 0 2
2 2 2 2 2

输出: 

34

说明:

有多种安放选择均可摧毁价值34，其中一种方案是炸弹放置在(3,1),(3,3),(3,5)

示例2

输入: 

8
10 15 3 3 12 16 7 2
1 6 19 19 1 12 19 14
7 0 6 3 15 1 16 2
13 7 12 5 2 9 2 5
13 0 14 6 19 10 9 1
0 13 1 1 14 15 7 7
1 12 3 16 12 14 12 9
11 15 16 14 1 12 1 8

输出: 

280

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 105ms, 内存消耗: 428K, 提交时间: 2022-02-26 15:47:21 

#include<iostream>
#include<cmath>
using namespace std;
int main(){
    long long n,i,j,a[105],k,l,sum,max=0;
    cin>>n;
    for(i=1;i<=n*n;i++){
        cin>>a[i];
    }
    if(n==1)max=a[1];
    for(i=1;i<=n*n;i++){
        for(j=i+1;j<=n*n;j++){
            for(k=j+1;k<=n*n;k++){
                sum=0;
                for(l=1;l<=n*n;l++){
                    if(l-i==2*n||l-i==n||i-l==2*n||i-l==n||l-k==2*n||l-k==n||k-l==2*n||k-l==n||l-j==2*n||l-j==n||j-l==2*n||j-l==n||abs(i-l)<=2&&(i-1)/n==(l-1)/n||abs(j-l)<=2&&(j-1)/n==(l-1)/n||abs(k-l)<=2&&(k-1)/n==(l-1)/n)
                        sum=sum+a[l];
                }
                if(sum>max)max=sum;
            }
        }
    }
    cout<<max;
}

上一题

© 2025 nowcoder.com