问题 M: 【动态规划】商店购物 时间限制: 1 Sec 内存限制: 64 MB
题目描述
魔法商店中每种商品都有一个价格。例如，一朵花的价格是2 元，一个花瓶的价格是5 元。为了吸引更多的顾客，商店提供了特殊优惠价。 特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如：3朵花的价格不是6元而是5 元；2个花瓶加1朵花是10 元不是12元。 编一个程序，计算某个顾客所购商品应付的费用。要充分利用优惠价以使顾客付款最小。请注意，你不能变更顾客所购商品的种类及数量，即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述，并且某顾客购买物品为3朵花和2个花瓶。那么顾客应付款为14 元。因为1朵花加2个花瓶的优惠价为10元；2朵花的正常价为4元。
输入 输入包括一些商店提供的优惠信息，接着是购物清单。 第一行为优惠商品的种类数（0≤ s ≤ 99）。 第二行到第s+1 行，每一行都用几个整数来表示一种优惠方式。第一个整数 n （1 ≤ n ≤ 5），表示这种优惠方式由 n 种商品组成。后面 n 对整数 c 和 k 表示 k （1≤ k ≤5）个编号为 c （1≤ c ≤ 999）的商品共同构成这种优惠，最后的整数 p 表示这种优惠的优惠价（1≤ p ≤ 9999）。优惠价总是比原价低。 第 s+2 行，这一行有一个整数 b （0≤ b ≤5），表示需要购买 b 种不同的商品。 第 s+3 行…第 s+b+2 行，这 b 行中的每一行包括三个整数：c ，k和 p 。c 表示唯一的商品编号（1 ≤ c ≤ 999），k 表示需要购买的 c 商品的数量（1≤k ≤5）。p 表示 c 商品的原价（1 ≤ p≤ 999）。最多购买 5×5=25 个商品。
输出 只有一行，输出一个整数：购买这些商品的最低价格。 样例输入
2 1 7 3 5 2 7 1 8 2 10 2 7 3 2 8 2 5
样例输出
14
思路：完全背包+状压
#include <bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair #define pii pair<int,int> using namespace std; struct youh { int n,p,w,sum,c[6],k[6]; }Y[110]; int n,s,ans,C[6],K[6],P[6],f[8000]; int findit(int cc) { for (int i=0;i<n;++i) if (C[i]==cc) return i; } int fun(int a,int b){ int s=0; for (int i=0;i<5;++i){ if (a%6>=b%6) s+=(int)pow(6,i)*(a%6-b%6); else return -1; a/=6; b/=6; } return s; } int main() { while (~scanf("%d",&s)){ for (int i=1;i<=s;++i) { scanf("%d",&Y[i].n); for (int j=0;j<Y[i].n;++j) scanf("%d%d",&Y[i].c[j],&Y[i].k[j]); scanf("%d",&Y[i].p); } scanf("%d",&n); int V=0,S=0; for (int i=0;i<n;++i) { scanf("%d%d%d",&C[i],&K[i],&P[i]); V+=K[i]*P[i]; S+=(int)pow(6,i)*K[i]; } for (int i=1;i<=s;++i) { int ss=0,sum=0; for (int j=0; j<Y[i].n; ++j) { ss+=P[findit(Y[i].c[j])]*(Y[i].k[j]); sum+=(int)pow(6,findit(Y[i].c[j]))*Y[i].k[j]; } Y[i].w=ss-Y[i].p; Y[i].sum=sum; } memset(f,0,sizeof f); for (int i=1;i<=s;++i) for (int v=0;v<7776;++v){ if (fun(v,Y[i].sum)==-1) continue; f[v]=max(f[v],f[fun(v,Y[i].sum)]+Y[i].w); } printf("%d\n",V-f[S]); } return 0; }