AOJ DPL_1 A Combinatiorial Coin Changing Problem
問題
解法
DPのプラクティスのセットのところの問題ですので当然DP。普通にDPを組むと何枚でも使用できるってのkを使用枚数の上限としてO(nmk)ってなるので間に合わない。たぶん正答率が低いのはこれでTLEが出てるからかと。
dp[i+1][j]の計算においてk(k>=1)個選ぶ場合は、dp[i+1][j-d[j]]の計算でk-1個選んだときの計算がされてるのでkに関するループを減らせる。
O(nm)で解けるようになり間に合う。
心臓に悪いコード
int dp[MAX_M+1][MAX_N+1]; int n, m, d[MAX_M]; int main(){ scanf("%d%d", &n, &m); rep(i, m) scanf("%d", d+i); rep(i, MAX_M+1) rep(j, MAX_N+1) dp[i][j] = INF; dp[0][0] = 0; rep(i, m){ rep(j, n+1){ dp[i+1][j] = min(dp[i][j], dp[i+1][j-d[i]] + 1); } } printf("%d\n", dp[m][n]); return 0; }