こちらも妙なひっかけはナシか。
http://codeforces.com/contest/598/problem/E
問題
N*Mのグリッド状のチョコレートがある。
このチョコレートを、セルの境目を一直線に割ることを何度か繰り返し、割ったチョコ群の一部を選んで総和がKになるようにしたい。
なお、チョコを1回割ると、その断面の長さの2乗のコストがかかる。
条件を満たすチョコの割り方の最小コストを求めよ。
解法
dp[高さN][幅M][残したいチョコの大きさK] := 最小コスト
としてメモ化再帰なりDPすればよい。
各状態では、どの縦または横のラインで2つに分けるか、また、残したいチョコの大きさKに対し片方はそのうちどれだけを生成するか、で二重ループして探索していけば良い。
int T; ll memo[31][31][51]; ll dodo(int a,int b,int k) { if(a*b==k || k==0) return 0; if(a*b<k) return 1LL<<60; if(a<b) swap(a,b); ll& ret=memo[a][b][k]; if(memo[a][b][k]>=0) return memo[a][b][k]; ret=1LL<<60; for(int w=1;w<=a/2;w++) for(int d=0;d<=k;d++) ret=min(ret,0LL+b*b+dodo(w,b,d)+dodo(a-w,b,k-d)); for(int h=1;h<=b/2;h++) for(int d=0;d<=k;d++) ret=min(ret,0LL+a*a+dodo(a,h,d)+dodo(a,b-h,k-d)); return ret; } void solve() { int i,j,k,l,r,x,y; string s; MINUS(memo); cin>>i; while(i--) { cin>>x>>y>>r; cout<<dodo(x,y,r)<<endl; } }
まとめ
Cの誤差ゲーとFのめんどくささが際立つ回でした。