BONUS spoj – VOI 2011 Phần thưởng

Nguồn đề bài: http://vn.spoj.com/problems/BONUS/

1. Đề bài BONUS Spoj

Tuấn là người chiến thắng trong một cuộc thi “tìm hiểu kiến thức vũ trụ” và được nhận các phần thưởng do công ty XYZ tài trợ. Các phần thưởng được bố trí trên một bảng hình vuông nxn có dạng một lưới ô vuông kích thước đơn vị. Các dòng của bảng được đánh số từ 1 đến n, từ trên xuống dưới và các cột của bảng được đánh số từ 1 đến n, từ trái qua phải. Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j) và trên ô đó chứa một món quà có giá trị là a[i,j]     (1 <= i, j <= n)

Đề nhận phần thưởng, Tuấn được phép chọn một hình vuông kích thước k x k chiếm trọn trong một số ô của bảng và nhận tất cả các phần quà có trong các ô nằm trong hình vuông đó.

Yêu cầu: Hãy xác định tổng giá trị lớn nhất của món quà mà Tuấn có thể nhận được.

Dữ liệu:

• Dòng thứ nhất chứa hai sô nguyên dương n, k (n <= 1000, n/3 <= k <= n).
• Dòng thứ i trong số n dòng tiếp theo chứa n số nguyên dương, số thứ j là a[i,j] (a[i,j] <= 1000)

Kết quả:

• Ghi ra một số nguyên duy nhất là tổng giá trị lớn nhất của các món quà mà Tuấn có thể nhận được.

Ví dụ:

          INPUT                                                                             OUTPUT

2. Thuật toán BONUS Spoj

Gọi F[i,j] là tổng các ô từ A[1,1] đến A[i,j].

Như vậy chúng ta xây dựng mảng F bằng: F[i,j]=F[i-1,j]+F[i,j-1]-F[i-1,j-1]+A[i,j];

oke, Sau khi xây dựng được mảng trên chúng ta sẽ mất O(n^2), nhưng để lấy tổng của 1 hình vuông có kích thước là k, với góc trên trái của hình vuông là ô i,j thì chúng ta chỉ mất O(1) để xác định ngay bằng công thức:

A[i,j]-A[i-k,j]-A[i,j-k]+a[i-k,j-k];

Dựa vào ý tưởng tính trước này chúng ta tiết kiệm được thời gian xử lí.

Độ phức tạp O(n^2)

3. Code tham khảo BONUS Spoj

a. code C++

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstring>

usingnamespace std;

long n,k;
long long res = 0 , t;
long long a[1010][1010];

int main()
{
    scanf("%li %li",&n,&k);
    for(long i=1;i<=n;i++)
        for(long j=1;j<=n;j++)
        {
            scanf("%lld",&a[i][j]);
            a[i][j] += a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }
    for(long i=k;i<=n;i++)
        for(long j=k;j<=n;j++)
        {
            t = a[i][j]+a[i-k][j-k]-a[i][j-k]-a[i-k][j];
            res = max(res,t);
        }
    printf("%lld",res);
    return0;
}

b. code pascal

const   fi='';
        nmax=1000;
type    data=longint;
var
        f:text;
        A:array[0..nmax+1,0..nmax+1] of longint;
        n,k:data;

procedure xuli;
var     i,j:data;
        res:data;
begin
        assign(f,fi); reset(f);
        readln(f,n,k);
        for i:=0 to n do
                begin
                        a[i,0]:=0;
                        a[0,i]:=0;
                end;
        res:=low(data);

        for i:=1 to n do
                for j:=1 to n do
                        begin
                                read(f,a[i,j]);
                                A[i,j]:=a[i,j]+a[i-1,j]+a[i,j-1]-a[i-1,j-1];
                        end;
        for i:=k to n do
                for j:=k to n do
                        if res<A[i,j]-A[i-k,j]-A[i,j-k]+a[i-k,j-k] then
                                res:=A[i,j]-A[i-k,j]-A[i,j-k]+a[i-k,j-k];
        writeln(res);
        close(f);
end;

begin
        xuli;
end.

bạn có thể thử sức với một bài tương tự:

http://www.spoj.com/THPTCBT/problems/YB_KT2B2/