Code Formula 2014 予選B : D - お釣りの嫌いな高橋君

DPで通した。
http://code-formula-2014-qualb.contest.atcoder.jp/tasks/code_formula_2014_qualB_d

問題

N種類の硬貨がある。i番の硬貨10枚分と(i+1)番の硬貨１枚は同じ価値である。
i番目の硬貨をA[i]枚持っているとき、表現できる金額が何通りか答えよ。

解法

公式回答とは別のDP解法で解いた。
DPで「今の桁のをある値にしたとき、それより上の桁で表現可能な金額は何通りあるか」を上の桁からDPしていく。

int N;
int A[70];
ll mo=1000000007;
ll memo[70][100000];

ll dfs(int d,int c) {
	if(d>=69) return 1;
	if(memo[d][c]>=0) return memo[d][c];
	int x;
	memo[d][c]=0;
	FOR(x,10) if(x<=c+A[d]) {
		memo[d][c]+=dfs(d+1,(c+A[d]-x)/10);
	}
	memo[d][c]%=mo;
	return memo[d][c];
	
}

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	MINUS(memo);
	cout << (dfs(0,0)+(mo-1))%mo << endl;
	
}

まとめ

最初DPじゃない方法で解こうと思ったけどうまく行かず、DPで解いた。
繰り上がりが影響する桁の範囲をグループにして考えればよかったのか。