程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hdu 1559 最大子矩陣(二維樹狀數組)

hdu 1559 最大子矩陣(二維樹狀數組)

編輯:關於C++

最大子矩陣

Time Limit: 30000/10000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3788Accepted Submission(s): 1926  
Problem Description 給你一個m×n的整數矩陣,在上面找一個x×y的子矩陣,使子矩陣中所有元素的和最大。
Input 輸入數據的第一行為一個正整數T,表示有T組測試數據。每一組測試數據的第一行為四個正整數m,n,x,y(0
Output 對於每組數據,輸出一個整數,表示子矩陣的最大和。
Sample Input

1 4 5 2 2 3 361 649 676 588 992 762 156 993 169 662 34 638 89 543 525 165 254 809 280

Sample Output

2474

Author lwg
Source HDU 2006-12 Programming Contest
二維樹狀數組模板題~~ 附上模板
void add(int x, int y, int d) {
    int i, j;
    for(i = x; i < N; i += lowbit(i))
        for(j = y; j < N; j += lowbit(j))
            mat[i][j] += d;
}

LL sum(int x, int y) {
    LL res = 0;
    int i, j;
    for(i = x; i > 0; i -= lowbit(i))
        for(j = y; j > 0; j -= lowbit(j))
            res += mat[i][j];
    return res;
}

該題主要注意一下sum的功能則是求從元素(1, 1)開始到(x, y)的總和,同樣,可以求出任意一個子矩陣內的所有元素之和,即sum(x2, y2) - sum(x1-1, y2) - sum(x2, y1-1) + sum(x1-1, y1-1)。
詳見代碼。
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int n,m;
int c[1010][1010];

int lowbit(int k)
{
    return k&(-k);
}

void add(int x,int y,int num)
{
    for (int i=x; i<=n; i+=lowbit(i))
    {
        for (int j=y; j<=m; j+=lowbit(j))
        {
            c[i][j]+=num;
        }
    }
}

int sum(int x,int y)
{
    int s=0;
    for (int i=x; i>0; i-=lowbit(i))
    {
        for (int j=y; j>0; j-=lowbit(j))
        {
            s+=c[i][j];
        }
    }
    return s;
}

int main()
{
    int t;
    int ans,kk;
    scanf("%d",&t);
    while (t--)
    {
        int Max=0;
        int x,y;
        scanf("%d%d%d%d",&n,&m,&x,&y);
        memset(c,0,sizeof(c));
        for (int i=1; i<=n; i++)
        {
            for (int j=1; j<=m; j++)
            {
                scanf("%d",&kk);
                add(i,j,kk);
            }
        }
        int k=1;
        for (int i=1; i+x-1<=n; i++)
        {
            for (int j=1; j+y-1<=m; j++)
            {
                ans=sum(i+x-1,j+y-1)-sum(i-1,j+y-1)-sum(i+x-1,j-1)+sum(i-1,j-1);
                if (Max<ans) max="ans;" pre="" printf="" return=""><p>
</p>
   
</ans)></cstring></cstdio></iostream>
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved