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); } }