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;
}