题意:有n(n<=5)种物品,每种个数num<=5,价值1<=val<=999,现在商店推出m(m<=99)种促销方案,即若干种物品放在一起价格会比单个物品的总和便宜,
问买到所有物品的最少花多少钱。
题解:因为n和num很小,所以想到n维dp,但是不好处理,想到用6进制6位表示状态,然后对每种促销方案做完全背包就好了。
Sure原创,转载请注明出处。
#include <iostream> #include <cstdio> #include <memory.h> #include <map> using namespace std; const int inf = 1 << 29; const int maxn = 8; const int maxm = 8000; const int val[maxn] = {1,6,36,216,1296,7776}; struct cargo { int num,val; }bag[maxn]; int dp[maxm],st[maxn],cur[maxn]; map <int , int> hash; int m,n,tot; inline int MIN(int a,int b) { return a < b ? a : b; } inline void in(int &a) { char ch; while(ch = getchar(), ch < '0' || ch > '9'); a = ch - '0'; while(ch = getchar(), ch >= '0' && ch <= '9') { a = a * 10 + ch - '0'; } return; } int load(int s[]) { int ans = 0; for(int i=1;i<=n;i++) { ans += val[i-1] * s[i]; } return ans; } void upload(int x,int s[]) { for(int i=1;i<=n;i++) { s[i] = x % 6; x /= 6; } return; } void read() { hash.clear(); int x; for(int i=1;i<=n;i++) { in(x),in(bag[i].num),in(bag[i].val); hash[x] = i; st[i] = bag[i].num; } tot = load(st); return; } void init() { for(int i=0;i<=tot;i++) { int res = 0; upload(i , st); for(int j=1;j<=n;j++) { if(st[j] > bag[j].num) { res = inf; break; } else { res += bag[j].val * st[j]; } } dp[i] = res; } return; } void update(int val) { for(int i=0;i<=tot;i++) { upload(i , st); bool flag = true; for(int j=1;j<=n;j++) { st[j] += cur[j]; if(st[j] > bag[j].num) { flag = false; break; } } if(flag) { int nxt = load(st); dp[nxt] = MIN(dp[nxt] , dp[i] + val); } } return; } void solve() { in(m); int num,x,c,p; while(m--) { memset(cur,0,sizeof(cur)); in(num); for(int i=0;i<num;i++) { in(x),in(c); x = hash[x]; cur[x] = c; } in(p); update(p); } printf("%d\n",dp[tot]); return; } int main() { while(~scanf("%d",&n)) { read(); init(); solve(); } return 0; }