PKU 2904 The Mailboxes Manufacturers Problem
http://poj.org/problem?id=2904
最大でm個の爆竹が入る郵便箱がk個ある。
この郵便箱は特定の個数以上の爆竹を同時に爆発させると壊れる。
郵便箱が何個の爆竹で壊れるかを知るために最低でもいくつの爆竹が必要かを求めろというような問題。
dp[残りの郵便箱][絶対に耐えられる個数][絶対に耐えられない個数-1]としてi個の爆竹で壊れた場合と、耐えた場合をメモ化再帰で計算しました。
int memo[11][110][110]; int rec(int k,int l,int r){ if(l>=r) return 0; if(k==1) return r*(r+1)/2-l*(l+1)/2; if(memo[k][l][r]) return memo[k][l][r]; int& ret=memo[k][l][r] = 1<<28; for(int i=l+1;i<=r;++i) ret=min(ret,max(rec(k,i,r),rec(k-1,l,i-1))+i); return ret; } void solve(){ int k,m; cin>>k>>m; cout<<rec(k,0,m)<<endl; } main(){ int n; cin>>n; rep(i,n) solve(); }