本文共 1971 字，大约阅读时间需要 6 分钟。
题目大意：有一个人要买b件商品，给出每件商品的编号，价格和数量，恰逢商店打折。有s种打折方式。问怎么才干使买的价格达到最低
解题思路：最多仅仅有五种商品。且每件商品最多仅仅有5个，所以能够用5维dp来表示。每一个维度都代表一件商品的数量
#include #include #include #include using namespace std;#define maxn 6#define maxs 200#define INF 0x3f3f3f3fstruct product{ int c, k, p;}pro[maxn];struct offer{ int num[maxn], price;}off[maxs];int b, s;int dp[maxn][maxn][maxn][maxn][maxn];map m;void init() { memset(dp, -1, sizeof(dp)); memset(off, 0, sizeof(off)); m.clear(); for(int i = 0; i < b; i++) { scanf("%d%d%d", &pro[i].c, &pro[i].k, &pro[i].p); m[pro[i].c] = i; off[i].num[i] = 1; off[i].price = pro[i].p; } if(b < 5) { for(int i = b; i < 5; i++) pro[i].k = pro[i].p = 0; } scanf("%d", &s); int n, c, k; for(int i = b; i < b + s; i++) { scanf("%d", &n); for(int j = 0; j < n; j++) { scanf("%d%d", &c, &k); off[i].num[m[c]] += k; } scanf("%d", &off[i].price); }}int dfs(int a1, int a2, int a3, int a4, int a5) { if(dp[a1][a2][a3][a4][a5] != -1) return dp[a1][a2][a3][a4][a5]; dp[a1][a2][a3][a4][a5] = INF; for(int i = 0; i < b + s; i++) { if(a1 >= off[i].num[0] && a2 >= off[i].num[1] && a3 >= off[i].num[2] && a4 >= off[i].num[3] && a5 >= off[i].num[4]) dp[a1][a2][a3][a4][a5] = min(dp[a1][a2][a3][a4][a5], off[i].price + dfs(a1-off[i].num[0],a2-off[i].num[1],a3-off[i].num[2],a4-off[i].num[3],a5-off[i].num[4])); } return dp[a1][a2][a3][a4][a5];}void solve() { dp[0][0][0][0][0] = 0; if(b == b + s) { int t = 0; for(int i = 0; i < 5; i++) t += pro[i].p * pro[i].k; printf("%d\n", t); } else printf("%d\n",dfs(pro[0].k, pro[1].k, pro[2].k, pro[3].k, pro[4].k));}int main() { scanf("%d", &b); init(); solve(); return 0;}
转载地址：http://uzhna.baihongyu.com/