AOJ : 1176 - 輪番停電計画 (Planning Rolling Blackouts)

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1176&lang=jp
日本語の問題文なので, 概要は省略します.

アルゴリズム

メモ化再帰で解きました.
ある長方形の範囲 (lx,ly)〜(hx,hy) において, グループの最大数・予備力は, 必ず一意に定まります.
これを利用して, 全ての区切り方を試行するDFSを書いた後, メモ化に書き変えましょう.
O(32^4)

あと, ある長方形の範囲の電力の合計を計算するのを, DFSするときに毎回毎回行っていると, 計算量がやばそうだと思ったので, あらかじめ簡易的なDPで計算しておきました.
O(32^4)

プログラム

typedef pair<int,int> P;

int h,w,s,all,t[32][32];
int rec[32][32][32][32]; //長方形の合計[ly][lx][hy][hx]
P dp[32][32][32][32]; //メモ化

//全ての(lx,ly)〜(hx,hy)の長方形合計を計算
void mkRec(){
  memset(rec,0,sizeof(rec));

  rep(i,h){
    rep(j,w){
      rec[i][j][i][j] = t[i][j];

      for(int y=i-1;y>=0;y--)
        rec[y][j][i][j] = rec[y+1][j][i][j] + t[y][j];

      for(int y=i;y>=0;y--){
        int sum = 0;
        for(int x=j;x>=0;x--){
          sum += rec[y][x][i][x];
          rec[y][x][i][j] = sum;
        }
      }
    }
  }
}

//戻り型 : P. first : 最大グループ数. second : 最大予備力
P dfs(int lx,int ly,int hx,int hy){
  if(dp[ly][lx][hy][hx].first != 0) return dp[ly][lx][hy][hx];

  P res = P(1,s-(all-rec[ly][lx][hy][hx]));

  //水平分割
  for(int i=ly;i<hy;i++){
    if(all - rec[ly][lx][i][hx] > s ||
       all - rec[i+1][lx][hy][hx] > s) continue;
    P a = dfs(lx,ly,hx,i);
    P b = dfs(lx,i+1,hx,hy);
    P cal = P(a.first+b.first,min(a.second,b.second));
    res = max(res,cal);
  }

  //垂直分割
  for(int j=lx;j<hx;j++){
    if(all - rec[ly][lx][hy][j] > s ||
       all - rec[ly][j+1][hy][hx] > s) continue;
    P a = dfs(lx,ly,j,hy);
    P b = dfs(j+1,ly,hx,hy);
    P cal = P(a.first+b.first,min(a.second,b.second));
    res = max(res,cal);
  }

  return dp[ly][lx][hy][hx] = res;
}

int main(void){
  while(scanf("%d%d%d",&h,&w,&s),h||w||s){
    all = 0;
    rep(i,h){
      rep(j,w){
        scanf("%d",&t[i][j]);
        all += t[i][j];
      }
    }

    mkRec();

    memset(dp,0,sizeof(dp));
    P p = dfs(0,0,w-1,h-1);
    printf("%d %d\n",p.first,p.second);
  }
}