東京工業大学プログラミングコンテスト2015 : F - レシート

ちょっと迷う問題。
http://ttpc2015.contest.atcoder.jp/tasks/ttpc2015_f

問題

A円の支払いに際し、A円以上任意のX円で支払いをすることが出来る。
請求額のA円、支払額のX円、おつりの(X-A)円を並べたとき、いずれも一致するような桁数最大値を求めよ。

解法

３つの数値がある桁で一致するのは以下のいずれか。

• いずれも0で、一つ下の位で繰り下がりが発生していない
• いずれも9で、一つ下の位で繰り下がりが発生している

dp[桁][繰り下がりの有無]:=一致する桁数の最大値 を状態として持ち、下の位から順に0～9を総当たりしながらDPしていく。
上記条件を満たす場合、一致する桁が１インクリメントされる。

注意点として、leading zeroの部分は答えの桁数にカウントされないことに留意する。

string A;
int ret;

int dp[1010][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(dp);
	cin>>A;
	dp[0][0]=0;
	FOR(i,A.size()) {
		j = A[A.size()-1-i]-'0';
		FOR(x,10) {
			dp[i+1][x>j]=max(dp[i+1][x>j],dp[i][0] +(j==0 && x==0));
			if(j-x>0 || i==0) ret=max(ret,dp[i+1][x>j]);
			dp[i+1][(x+1)>j]=max(dp[i+1][(x+1)>j],dp[i][1] +(j==9 && x==9));
			if(j!=(x+1) || i==0) ret=max(ret,dp[i+1][(x+1)>j]);
		}
	}
	cout<<ret<<endl;
}

まとめ

最初各桁0,9だけ調べればいいかと思ったけど、面倒で0-9総当たりした。