UVa 10898 : D: Combo Deal
UVa演習 2014/6/10 (火) 問2
問題リンク:http://uva.onlinejudge.org/external/108/10898.html
問題概要:
I種類の食べ物があり、それぞれの値段が与えられる
C種類のセットがあり、その値段も同様に与えられる
クエリーとして、I種類の食べ物をそれぞれ何個ずつ購入するのかが与えられるので
それらをちょうど購入する際にかかる費用を最小化せよ
解法:
vectorで各食べ物を何個購入したかを保存してDP
セットだけで作れる状態をあらかじめ全て作っておく
クエリー毎に(セットだけ+足りない分を単品で購入)を見て値段の最少値をとる
コード:
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) using namespace std; int single[10],query[10]; int multi[10][10]; int main(){ int I,C,Q; while( cin >> I ){ rep(i,I) cin >> single[i]; cin >> C; rep(i,C) rep(j,I+1) cin >> multi[i][j]; map<vector<int>,int> dp; dp[vector<int>(I,0)] = 0; rep(i,C){ map<vector<int>,int> tmp = dp; for(map<vector<int>,int>::iterator it = tmp.begin(); it != tmp.end(); it++){ vector<int> vec = it->first; int money = it->second; for(int j=0;j<10;j++){ money += multi[i][I]; rep(k,I){ vec[k] += multi[i][k]; if( vec[k] >= 10 ) goto Skip; } if( !dp.count(vec) ) dp[vec] = money; else dp[vec] = min(dp[vec],money); } Skip:; } } cin >> Q; rep(i,Q){ rep(j,I) cin >> query[j]; int mincost = INT_MAX; for(map<vector<int>,int>::iterator it = dp.begin(); it != dp.end(); it++){ vector<int> vec = it->first; int cost = it->second; rep(j,I){ if( vec[j] > query[j] ) goto Skip2; cost += (query[j]-vec[j]) * single[j]; } mincost = min(mincost,cost); Skip2:; } cout << mincost << endl; } } return 0; }