TopCoder SRM 437 Div1 Hard TheSum

問題

正の整数a, b, cが与えられる。
a + b = cが成り立つように、それぞれの数字を
数字を一つ削除するごとにコストdelCost
数字を一つ挿入するごとにコストinsCost
数字を一つ置換するごとにコストrepCostで、
何回でも削除、挿入、置換ができる。
ただし、できた数式のa, b, cは全て正の整数でなくてはならず、leadingzeroがあってはならない。

かかる最小のコストはいくらか求めよ。

制約条件

a, b, c≦10^9
コスト≦10^6

方針

下の一桁からマッチさせていくDP.
dp[aの何桁まで使ったか][bの何桁まで][cの何桁まで][aの状態][bの状態][cの状態][繰り上がり]
とすればよい。

leadingzeroをつけてしまったり、
aの数が終わっているのにその上空に数字をいきなりつけたりしてはいけないので、
状態を適切に持つ必要がある。
状態は、直前が0であるかそうでないかと、数字がすでに終わっているか。

数字が終わっている場合は、すでに0が入っていると考え、変更も挿入もできないようにする。

ソースコード

int insCost, delCost, repCost;
int da[11], db[11], dc[11], na, nb, nc;
int dp[12][12][12][3][3][3][2]; //a, b, c, flag, carry
//flag 0: zero 1: nonzero 2: finish

void parse(int n, int *a, int &m){
	m = 0;
	for(; n; n /= 10) a[m++] = n % 10;
}
int rec(int ai, int bi, int ci, int fa, int fb, int fc, int carry){
	int &res = dp[ai][bi][ci][fa][fb][fc][carry];
	if(res >= 0) return res;
	res = inf;
	
	if(ai == na && bi == nb && ci == nc && fa >= 1 && fb >= 1 && fc >= 1 && carry == 0){
		return res = 0;
	}
	if(ai == na && bi == nb && ci == nc) return res = inf;
	
	//del
	if(ai < na) res = min(res, rec(ai + 1, bi, ci, fa, fb, fc, carry) + delCost);
	if(bi < nb) res = min(res, rec(ai, bi + 1, ci, fa, fb, fc, carry) + delCost);
	if(ci < nc) res = min(res, rec(ai, bi, ci + 1, fa, fb, fc, carry) + delCost);
	
	//finish
	if(ai == na && fa == 1) res = min(res, rec(ai, bi, ci, 2, fb, fc, carry));
	if(bi == nb && fb == 1) res = min(res, rec(ai, bi, ci, fa, 2, fc, carry));
	if(ci == nc && fc == 1) res = min(res, rec(ai, bi, ci, fa, fb, 2, carry));
	
	rep(a, 10) rep(b, 10) rep(c, 10) if((a + b + carry) % 10 == c) rep(ins, 1 << 3){
		
		int ai2, bi2, ci2, fa2, fb2, fc2;
		int cost = __builtin_popcount(ins) * insCost;
		
		//finishのがある場合、コストただで0に変換するしかない
		if(fa == 2 && !(!(ins >> 0 & 1) && a == 0)) continue;
		if(fb == 2 && !(!(ins >> 1 & 1) && b == 0)) continue;
		if(fc == 2 && !(!(ins >> 2 & 1) && c == 0)) continue;
		
		//全部使い終わっていたら挿入するしかない
		if(fa != 2 && ai == na && !(ins >> 0 & 1)) continue;
		if(fb != 2 && bi == nb && !(ins >> 1 & 1)) continue;
		if(fc != 2 && ci == nc && !(ins >> 2 & 1)) continue;
		
		//コストたす
		if(fa != 2 && !(ins >> 0 & 1) && a != da[ai]) cost += repCost;
		if(fb != 2 && !(ins >> 1 & 1) && b != db[bi]) cost += repCost;
		if(fc != 2 && !(ins >> 2 & 1) && c != dc[ci]) cost += repCost;
		
		ai2 = min(na, ai + !(ins >> 0 & 1));
		bi2 = min(nb, bi + !(ins >> 1 & 1));
		ci2 = min(nc, ci + !(ins >> 2 & 1));
		
		if(fa == 2) fa2 = 2; else fa2 = a == 0 ? 0 : 1;
		if(fb == 2) fb2 = 2; else fb2 = b == 0 ? 0 : 1;
		if(fc == 2) fc2 = 2; else fc2 = c == 0 ? 0 : 1;
		
		res = min(res, rec(ai2, bi2, ci2, fa2, fb2, fc2, a + b + carry > 9) + cost);
	}
	return res;
}

class TheSum {
	public:
	int minCost(int a, int b, int c, int insCost, int delCost, int repCost) {
		memset(dp, -1, sizeof(dp));
		
		parse(a, da, na);
		parse(b, db, nb);
		parse(c, dc, nc);
		::insCost = insCost;
		::delCost = delCost;
		::repCost = repCost;
		
		return rec(0, 0, 0, 0, 0, 0, 0);
	}
};