TIOJ 1816 石油

TIOJ 1816 石油

題目概述:

給一個矩陣n*m，求3個k*k的正方形且不相交的元素和最大值。

思路:

待補QQ

//By SCJ

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

int n,m,k;

int a[1502][1502],pre[1502][1502],suf[1502][1502];

int pre_1[1502][1502],pre_2[1502][1502],pre_simple[1502][1502];

int suf_1[1502][1502];

void rot(int &n,int &m)

{

   int N=min(n,m),M=max(n,m);

   for(int i=1;i<=N;++i)

       for(int j=i+1;j<=M;++j) swap(a[i][j],a[j][i]);

   swap(n,m);

   for(int i=1;i<=n;++i)

       for(int j=1;j<=(m/2);++j)

           swap(a[i][j],a[i][m-j+1]);

}

void init()

{

   rot(n,m);

   memset(pre,0,sizeof(pre));

   memset(suf,0,sizeof(suf));

   for(int i=0;i<=1500;++i)

       for(int j=0;j<=1500;++j) pre_1[i][j]=pre_2[i][j]=suf_1[i][j]=-700000000;

   for(int i=1;i<=n;++i)

       for(int j=1;j<=m;++j)

           pre[i][j]=suf[i][j]=a[i][j];

   for(int i=1;i<=n;++i)

       for(int j=1;j<=m;++j) pre[i][j]+=pre[i][j-1];

   for(int j=1;j<=m;++j)

       for(int i=1;i<=n;++i) pre[i][j]+=pre[i-1][j];

   for(int i=n;i>=1;--i)

       for(int j=m;j>=1;--j) suf[i][j]+=suf[i][j+1];

   for(int j=m;j>=1;--j)

       for(int i=n;i>=1;--i) suf[i][j]+=suf[i+1][j];

}

void find_1()

{

   for(int i=k;i<=n;++i)

   {

       for(int j=k;j<=m;++j)

       {

           pre_simple[i][j]=pre[i][j]-pre[i-k][j]-pre[i][j-k]+pre[i-k][j-k];

           pre_1[i][j]=max({pre_1[i-1][j],pre_1[i][j-1],pre_simple[i][j]});

       }

   }

   for(int i=n-k+1;i>=1;--i)

   {

       for(int j=m-k+1;j>=1;--j)

       {

           int tp=suf[i][j]-suf[i+k][j]-suf[i][j+k]+suf[i+k][j+k];

           suf_1[i][j]=max({suf_1[i+1][j],suf_1[i][j+1],tp});

       }

   }

}

void find_2()

{

   for(int i=k;i<=n;++i)

       for(int j=k;j<=m;++j)

           pre_2[i][j]=max(pre_1[i-k][j],pre_1[i][j-k])+pre_simple[i][j];

   for(int i=k;i<=n;++i)

       for(int j=k;j<=m;++j)

           pre_2[i][j]=max({pre_2[i][j],pre_2[i-1][j],pre_2[i][j-1]});

}

int solve()

{

   int res=0;

   for(int i=k;i<=n;++i)

   {

       for(int j=k;j<=m;++j)

       {

           int tp=pre_2[i][j]+max(suf_1[1][j+1],suf_1[i+1][1]);

           res=max(res,tp);

       }

   }

   return res;

}

main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   cin>>n>>m>>k;

   for(int i=1;i<=n;++i)

       for(int j=1;j<=m;++j)

           cin>>a[i][j];

   init();

   int ans=solve();

   for(int r=0;r<3;++r)

   {

       init();

       find_1();

       find_2();

       ans=max(ans,solve());

   }

   cout<<ans<<endl;

}