2016年5月11日 星期三

UVA 10360 Rat Attack

/*
    題目連結  

    爆炸半徑為d的炸彈
    爆炸範圍會是個 邊長2*d+1的方形
    我們把這數字記作r

    因為我們要讓 爆炸中心的x和y越小越好
    所以我們知道最優的方形的右下角 必定在(0~1024,0~1024)這個範圍內
    (否則會有一個這樣的方形比它更優)
    因次我們枚舉右下角 看看哪個 r*r的方形最好

    但r*r的方形內的數字總和要怎麼求呢?
    硬加顯然是會超過時限的
    仔細看看會發現相鄰的方形會有很多數字重複
    利用這點 我們可以很快速的維護每一行 第i-r+1~i列 的數字和
    然後同理可以很快速的維護 第j-r+1~j行 在上述的列數範圍內的數字和
    (也就是我們關心的方形內的數字總和)

    不過要注意 因為題目要求爆炸中心要在(0~1024,0~1024)這個範圍內
    所以我們把右下角 還原成中心的時候
    要把其x,y座標和0取max
*/
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

int rats[1025][1025];
int sum_of_col[1025];

int main()
{
    int t;
    scanf("%d", &t);

    while( t-- )
    {
        memset(rats, 0, sizeof(rats));
        memset(sum_of_col, 0, sizeof(sum_of_col));

        int d;
        scanf("%d", &d);
        int r = d*2+1;

        int n;
        scanf("%d", &n);

        for(int ni = 0; ni < n; ni++)
        {
            int x, y, size;
            scanf("%d %d %d", &x, &y, &size);
            rats[x][y] += size;
        }

        int ans = 0, x = 0, y = 0;

        for(int i = 0; i < 1025; i++)
        {
            for(int j = 0; j < 1025; j++)
            {
                sum_of_col[j] += rats[i][j];
                if( i >= r ) sum_of_col[j] -= rats[i-r][j];
            }

            int sum = 0;

            for(int j = 0; j < 1025; j++)
            {
                sum += sum_of_col[j];
                if( j >= r ) sum -= sum_of_col[j-r];

                if( ans < sum )
                {
                    ans = sum;
                    x = i, y = j;
                }
            }
        }

        printf("%d %d %d\n", max(0, x-d), max(0, y-d), ans);
    }
}

沒有留言:

張貼留言