Codeforces ECR #001 : E. Chocolate Bar

こちらも妙なひっかけはナシか。
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のめんどくささが際立つ回でした。