PKU 2951 Cake Cutting
http://poj.org/problem?id=2951
w*hの大きさの長方形をm-1回のカットでm個に分ける。
分けられたピースのうち最大の大きさが最小になるときのその大きさを求めろというような問題。
dp[縦][横][あと何回切れるか]=最大値の最小値
でメモ化再帰しました。
切れる回数と何個に切るかを同じと考えてWAもらいました。
int memo[30][30][500]; int rec(int w,int h,int m){ if(w<h)swap(w,h); if(memo[w][h][m])return memo[w][h][m]; int& ret=memo[w][h][m]=w*h; if(m==0)return ret; rep(i,2){ for(int i=1;i<w;++i) for(int j=0;j<m;++j) if(i*h>=j && (w-i)*h>=m-1-j) ret=min(ret, max(rec(i,h,j),rec(w-i,h,m-1-j))); swap(w,h); } return ret; } main(){ int w,h,m; while(cin>>w>>h>>m,w) cout<<rec(w,h,m-1)<<endl; }