土下座しながら探索中

主に競技プログラミング

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