AtCoder ARC #005 We have nothing to do with him

問題

日本語なので本文参照（http://arc005.contest.atcoder.jp/tasks/arc005_4）

制約条件

priceは10^18以下
使えるボタンに0, 1は必ず含まれている。

方針

動的計画法による。
dp[i][j][k]を、先頭からi桁までを入力していて、
前の桁の余りがjあって、和の形の項の数がk個であるときの、ボタンの押下回数の最小値とする。
（ただし、+, =の回数は含めていない）

このとき、今の桁の数字を合計でいくつにするかで更新ができる。
数字の合計に対して、その合計を作るようなキーの押下回数の最小値は、
これもまた前処理でDPしておいて求める。

DPが終わったら、経路復元する。
j, kは適当に大きく取ったが、最小でいくつまで必要なのかはよくわかってない。

ソースコード

int bs[10], n, d[20], m;
int dp[30][300][50];
ll prev[30][300][50], mn[3100], pv[3100];
int ans[100][100];

void make(int ti, int tj, int tk){
	if(ti <= 0) return;
	int l = prev[ti][tj][tk] / 50 / 300;
	int pj = prev[ti][tj][tk] % (50 * 300) / 50;
	int pk = prev[ti][tj][tk] % 50;
	
	int tmp = l, c = 0;
	while(tmp > 0){
		ans[ti - 1][c++] = bs[pv[tmp]];
		tmp -= bs[pv[tmp]];
	}
	make(ti - 1, pj, pk);
}

int main()
{
	string s, t;
	cin >> s >> t;
	n = s.size();
	rep(i, n) bs[i] = s[i] - '0';
	
	m = t.size();
	rep(i, m) d[i] = t[i] - '0';
	
	rep(i, 30) rep(j, 300) rep(k, 50) dp[i][j][k] = inf;
	rep(i, 3100) mn[i] = inf;
	mn[0] = 0;
	rep(i, 3100) rep(j, n)
		if(i - bs[j] >= 0 && mn[i] > mn[i - bs[j]] + 1)
		mn[i] = mn[i - bs[j]] + 1, pv[i] = j;
	
	dp[0][0][0] = 0;
	rep(i, m) rep(j, 300) rep(k, 50) if(dp[i][j][k] != inf){
		int num = j * 10 + d[i];
		rep(l, 3100){
			int nj = num - l;
			if(nj >= 300 || nj < 0) continue;
			int use = mn[l], nxt = dp[i][j][k];
			int nk = max(k, use);
			if(use >= 50) continue;
			nxt += nk;
			if(dp[i + 1][nj][nk] > nxt)
			dp[i + 1][nj][nk] = nxt, prev[i + 1][nj][nk] = l * 50ll * 300 + j * 50 + k;
		}
	}
	
	int a = inf, ansi;
	rep(i, 50){
		int tmp = 0;
		if(i != 1) tmp += i ? i : 1;
		if(a > dp[m][0][i] + tmp)
		a = dp[m][0][i] + tmp, ansi = i;
	}
	make(m, 0, ansi);
	
	vector<string> res;
	rep(i, ansi){
		ll tmp = 0;
		rep(j, m) tmp *= 10, tmp += ans[j][i];
		stringstream ss;
		ss << tmp;
		res.pb(ss.str());
	}
	if(res.empty()) res.pb("0");
	
	if(res.size() == 1) cout << res[0] << endl;
	else{
		rep(i, res.size()) cout << res[i] << (i == (int)res.size() - 1 ? "=\n" : "+");
	}
	
	return 0;
}