UVa-10626 : Buying Coke
問題概要
8円のコーラをN(<150)本買いたい。1円玉をn_1(<500)枚、5円玉をn_5(<100)枚、10円玉をn_10(<50)枚持っている。1本ずつコーラを買う。おつりは最小枚数で支払われる。このとき、コインを自販機の口に入れる回数を最小化する問題。
解法
動的計画法。dp[i本買った][残り1円][残り5円][残り10円]=最小枚数とすると状態数が多くてTLEしそう。残り硬貨の枚数を全部覚えておく必要はなくて、2種類について枚数が分かれば残りの枚数は引き算で求められる。これで状態数が減って通るようになる。ただし残り5円の枚数は途中で初期値より増えることがありうるので注意。
acceptされたコード
計算量O(MAX_C * (MAX_50+MAX_100) * MAX_100)。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX_50 = 100; const int MAX_100 = 50; const int MAX_C = 150; const int INF = 1<<29; int dp[MAX_C+1][MAX_50+MAX_100+1][MAX_100+1]; int A, B, C, X; void init(){ scanf("%d%d%d%d", &X, &A, &B, &C); } int solve(){ for(int i=0; i<=X; i++){ for(int j=0; j<=B+C; j++){ for(int k=0; k<=C; k++){ dp[i][j][k] = INF; } } } int total = A + B*5 + C*10; dp[0][B][C] = 0; for(int i=0; i<X; i++){ for(int b=0; b<=B+C; b++){ for(int c=0; c<=C; c++)if(dp[i][b][c] < INF){ int a = total - b*5 - c*10; if(a >= 8){ dp[i+1][b][c] = min(dp[i+1][b][c], dp[i][b][c] + 8); } if(a >= 3 && b >= 1){ dp[i+1][b-1][c] = min(dp[i+1][b-1][c], dp[i][b][c] + 4); } if(b >= 2){ dp[i+1][b-2][c] = min(dp[i+1][b-2][c], dp[i][b][c] + 2); } if(c >= 1){ dp[i+1][b][c-1] = min(dp[i+1][b][c-1], dp[i][b][c] + 1); } if(c >= 1 && a >= 3){ dp[i+1][b+1][c-1] = min(dp[i+1][b+1][c-1], dp[i][b][c] + 4); } if(c >= 1 && b >= 1){ dp[i+1][b-1][c-1] = min(dp[i+1][b-1][c-1], dp[i][b][c] + 2); } } } total -= 8; } int ans = INF; for(int i=0; i<=B+C; i++){ ans = min(ans, *min_element(dp[X][i], dp[X][i] + C+1)); } return ans; } int main(){ int T; scanf("%d", &T); while(T--){ init(); printf("%d\n", solve()); } return 0; }