AtCoder ABC #155 : E - Payment

今回Fの正答率低かったみたいね。
https://atcoder.jp/contests/abc155/tasks/abc155_e

問題

10の累乗の紙幣のみある通貨を考える。
N円を支払うとき、支払う紙幣の枚数とお釣りの紙幣の枚数の合計の最小値を求めよ。

解法

下の桁から見ていくことにする。
選択肢は二つあって、今10^dの位を見ているとき、

• その桁をぴったり払い切る
• 1つ上の貨幣(10^(d+1))を払い、お釣りをもらう

後者の場合、上の桁で(10^(d+1))円だけ余分に支払わなければならない。
それぞれのケースを考え下の桁からDPしていけばよい。

int N;
string S;

int dp[2][2020202];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	reverse(ALL(S));
	S+=string(1000005,'0');
	
	dp[0][0]=0;
	dp[1][0]=1<<30;
	
	FOR(i,1000005) {
		
		dp[0][i+1]=min(dp[0][i]+S[i]-'0',dp[1][i]+(S[i]-'0'+1));
		dp[1][i+1]=min(dp[0][i]+10-(S[i]-'0'),dp[1][i]+10-(S[i]-'0'+1));
	}
	
	cout<<dp[0][1000004]<<endl;
	
	
}

まとめ

同じような問題過去に見てそうな気はする。