|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
#include <iostream> #include <cstdio> #include <queue> #include <sstream> #include <string> #include <cstring> #include <cmath> #define INF 100000000 #define ll long long using namespace std; int MX,cnt; int Item,Combo,noOfOrder; ll bestDp[1000000]; ll packPrice[1000000]; int packages[20]; void init() { cnt=0; for(int i=0;i<1000000;i++) { bestDp[i]=INF; packPrice[i]=0; } for(int i=0;i<20;i++) packages[i]=0; } ll _min(ll a,ll b) { if(a<b) return a; return b; } int isContain(int order,int packs) { if(packs>order) return 0; while(order>0 && packs>0) { if(order%10 < packs%10) return 0; order/=10; packs/=10; } return 1; } int _pow(int a,int p) { if(p==0) return 1; else return (_pow(a,p-1)*a); } void DP() { for(int order=1;order<1000000;order++) { for(int i=0;i<cnt;i++) { if(isContain(order,packages[i])) { bestDp[order]=_min(bestDp[order],bestDp[order-packages[i]] + packPrice[packages[i]] ); } } } } int main() { int a,idx,multiplier,val; int Orders; while(scanf("%d",&Item)!=EOF) { init(); for(int i=0;i<Item;i++) { idx = _pow(10,i); scanf("%lld",&packPrice[idx]); bestDp[idx]=packPrice[idx]; packages[cnt]=idx; cnt+=1; } scanf("%d",&Combo); for(int i=0;i<Combo;i++) { idx=0; for(int j=0;j<Item;j++) { scanf("%d",&a); multiplier=_pow(10,j); a=a*multiplier; idx+=a; } scanf("%lld",&packPrice[idx]); packages[cnt]=idx; bestDp[idx]=_min(bestDp[idx],packPrice[idx]); cnt+=1; } scanf("%d",&noOfOrder); DP(); for(int II=0;II<noOfOrder;II++) { val = 0; for(int JJ=0;JJ<Item;JJ++) { scanf("%d",&a); multiplier=_pow(10,JJ); a=a*multiplier; val+=a; } Orders=val; printf("%lld\n",bestDp[Orders]); } } return 0; } |