SRM 357 250pt : Hotel

keyword

動的計画法　C++

問題概要

バナナがK[i]本A[i]円(K[i], A[i] < 100, i<50)で売られている。バナナをN(<1000)本以上買うには最低何円必要か。

解法

典型的DP。計算量O(M*N^2)(M=Aの長さ)。

#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 1001;
const int INF = 1<<29;
int dp[MAX_N];

struct Hotel {

	int marketCost(int minCustomers, vector <int> customers, vector <int> cost) {
		fill(dp, dp+(minCustomers+1), INF);
		dp[0] = 0;
		int N = cost.size();
		for(int i=0; i<minCustomers; i++)if(dp[i] < INF){
			for(int j=0; j<N; j++){
				for(int k=1; ; k++){
					int next = min(minCustomers, i + customers[j]*k);
					dp[next] = min(dp[next], dp[i] + cost[j]*k);
					if(next == minCustomers) break;
				}
			}
		}
		return dp[minCustomers];
	}

};