intellij idea下载 CGLib动态代理 mysql 深度图像 劝酒文化 parsing templates events mono vue提交表单 react脚手架搭建 传智播客python short几个字节 cpm怎么计算 windows查看进程命令 office配置进度 python迭代器 python环境安装教程 如何配置python环境 python返回函数 python模块下载 python写入文件 java方法的重载 java自学教程 java8时间 java语言代码大全 javaworld corelpainter ** js数组移除指定元素 vfloppy 程序卸载 ps反选 无线网改密码 华为工具箱 maya骨骼绑定教程 清华天河 小米自动开关机 python列表去重 聊呗电脑版
当前位置: 首页 > 学习教程  > 编程语言

二维前缀和——激光问题Acwing99

2020/9/19 13:46:58 文章标签:

激光问题

题目:
地图上有 N 个目标,用整数Xi,Yi表示目标在地图上的位置,每个目标都有一个价值Wi。

注意:不同目标可能在同一位置。

现在有一种新型的激光炸弹,可以摧毁一个包含 R×R 个位置的正方形内的所有目标。

激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆炸范围,即那个正方形的边必须和x,y轴平行。

求一颗炸弹最多能炸掉地图上总价值为多少的目标。

输入格式
第一行输入正整数 N 和 R ,分别代表地图上的目标数目和正方形的边长,数据用空格隔开。

接下来N行,每行输入一组数据,每组数据包括三个整数Xi,Yi,Wi,分别代表目标的x坐标,y坐标和价值,数据用空格隔开。

输出格式
输出一个正整数,代表一颗炸弹最多能炸掉地图上目标的总价值数目。

数据范围
0≤R≤10^9
0<N≤10000,
0≤Xi,Yi≤5000
0≤Wi≤1000
输入样例:
2 1
0 0 1
1 1 1
输出样例:
1

该题是一个值得思考的二维前缀和问题。思维巧妙,将以(x, y)为爆炸中心点的情况,转移至以(x, y)为右下角思考左上方的总体情况,这种思想在前缀和和动态规划有可能会出现。

/*
求一个矩形范围的总价值,由此可以想到求前缀和降低复杂度
若每个范围的总价值用暴力求解 m 次 时间复杂度为 O( m * N ^ 2 )
使用前缀和时间复杂度为 O(N ^ 2)
*/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 5050;//点的坐标最大为5000
int f[N][N];//记录输入时每个点的总价值,同时也是二维前缀和数组——记录以(x, y)为右下角范围的前缀和。

int main(){
    memset(f, 0,sizeof(f));//初始化数组
    int N , R;//N 为目标数,R为炸弹轰炸的边长
    cin >> N >> R;
    int n = R , m = R;//n, m分别为炸弹爆炸点的右下角边界
    for(int i = 0 ,x, y,w;i < N ;i++){
        cin >> x >> y >> w;//(x,y)上有价值为w的目标
        x++, y++;//从1 ~ N 则前缀和不必要处理边界问题
        n = max(n ,x);
        m = max(m ,y);//更新边界
        f[x][y] += w;//更新该点的总价值
    }
    for(int i = 1; i <= n;i++){
        for(int j = 1; j <= m;j++){
            f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];//求取前缀和
        }
    }
    
    int ans = 0;//记录最大价值
    for(int i = R ;i <= n;i ++){
        for(int j = R ;j <= m ;j++){
            //将爆炸中心点转移至以(i, j)为右下的最上方爆炸范围处理。便于处理边长为奇数时的情况
            ans = max(ans, f[i][j] - f[i - R][j] - f[i][j - R] + f[i - R][j - R]);
        }
    }
    cout << ans << endl;
    return 0;
}

本文链接: http://www.dtmao.cc/news_show_200069.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?