AOJ1176 輪番停電計画

問題ページ Planning Rolling Blackouts | Aizu Online Judge

解法

func(sx,sy,gx,gy) = (指定範囲で実現できる最大のグループ数, グループの需要のうち最大) とする。その領域を分割しないか、縦に分割するか、横に分割するかの3通りの遷移がある。
分割しない場合はグループ数が1、需要の最大はその範囲の値の合計となる。ある矩形範囲の値の合計を求めるのには累積和を用いることでO(1)でできる。
ある二つの領域に分割したときは(グループ数の和,グループの需要の最大のうち小さい方)がその分割をマージした結果となる。
分割の方法は縦にO(W)通り、横にO(H)通り存在するので遷移がO(H+W)通り存在する。状態数がO((HW)^2)で遷移がO(H+W)なので32^5程度なので通る。

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define PB push_back

const int INF = (1LL<<30);

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

const int maxh = 35, maxw = 35;
int csum[maxh][maxw];
void init(VVI vec) {
  assert(vec.size());
  REP(i, vec.size()) REP(j, vec[0].size()) {
    if(!i && !j) csum[i][j] = vec[i][j];
    else if(!i) csum[i][j] = csum[i][j-1] + vec[i][j];
    else if(!j) csum[i][j] = csum[i-1][j] + vec[i][j];
    else csum[i][j] = csum[i-1][j] + csum[i][j-1] - csum[i-1][j-1] + vec[i][j];
  }
}
// 閉区間, 0-indexedで矩形範囲の合計
int cumsum(int sx, int sy, int gx, int gy) {
  if(!sx && !sy) return csum[gy][gx];
  if(!sx) return csum[gy][gx] - csum[sy-1][gx];
  if(!sy) return csum[gy][gx] - csum[gy][sx-1];
  return csum[gy][gx] - csum[gy][sx-1] - csum[sy-1][gx] + csum[sy-1][sx-1];
}

int h, w, s;
PII dp[35][35][35][35];
PII func(int sx, int sy, int gx, int gy) {
  if(dp[sx][sy][gx][gy] != PII{-1, -1}) return dp[sx][sy][gx][gy];
  // 分割しなかったとしても条件を満たさない
  if(cumsum(0, 0, w-1, h-1) - cumsum(sx, sy, gx, gy) > s) return {-1, -1};
  // 分割しない
  int group = 1, ret = cumsum(sx, sy, gx, gy);
  // 縦で割る
  FOR(i, sx, gx) {
    PII vl = func(sx, sy, i, gy);
    PII vr = func(i+1, sy, gx, gy);
    if(group < vl.first + vr.first || (group == vl.first+vr.first && ret < min(vl.second, vr.second))) {
      group = vl.first + vr.first;
      ret = min(vl.second, vr.second);
    }
  }
  // 横で割る
  FOR(i, sy, gy) {
    PII vl = func(sx, sy, gx, i);
    PII vr = func(sx, i+1, gx, gy);
    if(group < vl.first + vr.first || (group == vl.first+vr.first && ret < min(vl.second, vr.second))) {
      group = vl.first + vr.first;
      ret = min(vl.second, vr.second);
    }
  }
  return dp[sx][sy][gx][gy] = {group, ret};
}

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(true) {
    cin >> h >> w >> s;
    if(!h) break;
    VVI vec(h, VI(w));
    REP(i, h) REP(j, w) cin >> vec[i][j];

    // 累積和,dp配列の初期化
    init(vec);
    REP(i1, 35) REP(i2, 35) REP(i3, 35) REP(i4, 35) dp[i1][i2][i3][i4] = {-1, -1};

    PII ret = func(0, 0, w-1, h-1);
    cout << ret.first << " " << s - cumsum(0,0,w-1,h-1) + ret.second << endl;
  }

  return 0;
}