土下座しながら探索中

主に競技プログラミング

第2回 ドワンゴからの挑戦状 予選 D : 庭園

問題リンク :
D: 庭園 - 第2回 ドワンゴからの挑戦状 予選 | AtCoder

問題概要 :

解法 :
長方形を2つ選ぶので、縦か横に領域を分割して
それらの中の最大値を足したものの最大値が答えとなる
そのため、ある長方形の中の最大値について求めることができれば良い

まず、以下の問題を解こう
Frame | Aizu Online Judge
y軸を2つ選ぶというアイデアを得ましたね
では次に、以下の問題を解きましょう
https://uva.onlinejudge.org/external/126/p12640.pdf
(この解説は
UVa 12640 : Largest Sum Game - 土下座しながら探索中

数列について、連続した部分の総和の最大値の求めかたが分かりましたね
ではもうこの問題についても分かったでしょう



つまり、y軸を2つ固定すると、その固定された範囲の各x軸については和をとってまとめることが可能で、こうするとただの数列の連続した部分列の最大値を求める問題になります


コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;
const ll LLINF = LLONG_MAX;
const int MAX = 310;

ll b[MAX][MAX],sum[MAX][MAX];
ll upper[MAX], bottom[MAX];

void rotate90(int h,int w){
  swap(h,w);
  vector<vector<ll> > ret(h,vector<ll>(w,0));
  for(int y=0;y<h;y++){
    for(int x=0;x<w;x++){
      ret[y][x] = b[w-1-x][y];
    }
  }
  rep(i,h) rep(j,w) b[i][j] = ret[i][j];
}

inline ll calcSum(int x1,int y1,int x2,int y2) {
  ll ret = sum[y2][x2];
  if( y1-1 >= 0 ) ret -= sum[y1-1][x2];
  if( x1-1 >= 0 ) ret -= sum[y2][x1-1];
  if( y1-1 >= 0 && x1-1 >= 0 ) ret += sum[y1-1][x1-1];
  return ret;
}

ll calc(int h,int w) {
  rep(i,h) rep(j,w) {
    sum[i][j] = b[i][j];
    if( j-1 >= 0 ) sum[i][j] += sum[i][j-1];
    if( i-1 >= 0 ) sum[i][j] += sum[i-1][j];
    if( j-1 >= 0 && i-1 >= 0 ) sum[i][j] -= sum[i-1][j-1];
  }
  rep(i,h) upper[i] =  bottom[i] = -LLINF;
  rep(y1,h) REP(y2,y1,h) {
    ll maxi = -LLINF;
    ll mini = 0;
    rep(x,w) {
      maxi = max(maxi,calcSum(0,y1,x,y2)-mini);
      mini = min(mini,calcSum(0,y1,x,y2));
    }
    upper[y2]  = max(maxi,upper[y2]);
    bottom[y1] = max(maxi,bottom[y1]);
  }
  REP(y,1,h) upper[y] = max(upper[y],upper[y-1]);
  for(int y=h-2;y>=0;y--) bottom[y] = max(bottom[y],bottom[y+1]);
  ll maxi = -LLINF;
  rep(y,h-1) maxi = max(maxi,upper[y]+bottom[y+1]);
  return maxi;
}

void compute(int h,int w) {
  ll maxi = calc(h,w);
  rotate90(h,w);
  swap(h,w);
  maxi = max(maxi,calc(h,w));
  cout << maxi << endl;
}

int main() {
  int h,w;
  cin >> h >> w;
  rep(i,h) rep(j,w) cin >> b[i][j];
  compute(h,w);
  return 0;
}