程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1559 最大子矩陣 (DP)

HDU 1559 最大子矩陣 (DP)

編輯：C++入門知識

HDU 1559 最大子矩陣 (DP)

題目地址：HDU 1559

構造二維前綴和矩陣。即矩陣上的點a[i][j]表示左上方的點為(0,0)，右下方的點為(i,j)的矩陣的和。然後枚舉每個矩陣的左上方的點，由於矩陣的長和寬是固定的，那麼這個矩陣實際上也已經固定了。此時這個矩陣的和用公式：
sum=a[i+x-1][j+y-1]-a[i+x-1][j-1]-a[i-1][j+y-1]+a[i-1][j-1];

取最大值就可以了。

代碼如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
#define LL __int64
LL a[1001][1001];
int main()
{
    int t, n, m, i, j, k, x, y;
    LL z, max1;
    scanf("%d",&t);
    while(t--)
    {
        max1=-1;
        scanf("%d%d%d%d",&n,&m,&x,&y);
        memset(a,0,sizeof(a));
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                scanf("%I64d",&z);
                a[i][j]=a[i][j-1]+z;
            }
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                a[i][j]+=a[i-1][j];
            }
        }
        for(i=1;i<=n-x+1;i++)
        {
            for(j=1;j<=m-y+1;j++)
            {
                z=a[i+x-1][j+y-1]-a[i+x-1][j-1]-a[i-1][j+y-1]+a[i-1][j-1];
                if(max1