31
2019
07

noip2014 day1t3 无线网络发射器选址

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int map[130][130],d, n,;
long long sum[130][130],  ans, cnt;
void init() { //前缀和预处理
    int a, b, c;
    for(int i = 1; i <= n; ++i) {
        scanf("%d%d%d", &a, &b, &c);
        map[a][b] = c;//存储x,y路口的公共场所数 
    }
    //预处理二维前缀和 ,区间覆盖的公共场所数 
    for(int i = 0; i <= 128; ++i) {
        for(int j = 0; j <= 128; ++j) {
            sum[i][j] = (sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + map[i][j]);
        }
    }
}
//求区间x1y1到x2y2的和 
int getmany(int x1, int y1, int x2, int y2) { //前缀和查询
    return sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
}
void cross(int x, int y) { //查询(x,y)为中心的正方形权值并更新结果
    int x1, x2, y1, y2;
        //边界判断
    x1 = (x - d >= 0) ? (x - d) : 0;
    y1 = (y - d >= 0) ? (y - d) : 0;
    x2 = (x + d <= 128) ? (x + d) : 128;
    y2 = (y + d <= 128) ? (y + d) : 128;
    int tmp = getmany(x1, y1, x2, y2);//求区间和 
    if(tmp == ans) ++cnt; //更新方案数 
    if(tmp > ans) cnt = 1, ans = tmp;//更新最大 
}
int query() {
        //枚举(x,y)为中心的正方形
    for(int i = 0; i <= 128; ++i) {
        for(int j = 0; j <= 128; ++j) {
            cross(i, j);//每个点进行尝试 
        }
    }
    return ans;
}
int main() {
    scanf("%d%d", &d, &n);
    init();
    query();
    printf("%lld %lld\n",cnt , ans);
    return 0;
}


« 上一篇 下一篇 »

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。