本文共 2135 字，大约阅读时间需要 7 分钟。
/* @@2013-02-06 23:07
*/
题目大意：
题目给出商品数量不超过5，用5元组表示商品i的购买数量。优惠政策也不超过99
因此用f[a1][a2][a3][a4][a5]表示第i种商品买ai的数量的最小费用
用s[i][j]表示第i种政策j件物品的购买数量，s[i][0]表示政策i的优惠价格
重新处理商品的编号为输入的顺序。用map<int, int>实现
状态转移方程：f[a1][a2][a3][a4][a5]=min{f[a1-s[i][1]][a2-s[i][2]][a3-s[i][3]][a4-s[i][4]][a5-s[i][5]]+s[i][0]};
代码如下：
#include #include #include #include using namespace std;int f[6][6][6][6][6], s[100][6], cost[6], ni[6];// ni[i]表示i商品购买的数量， cost[i]表示i商品花费，s[i]i优惠政策 int main(){ int n, m, i, a1, a2, a3, a4, a5, num, mm, j, c, k; while(scanf("%d", &n)!=EOF) //n：商品数量 { map M; memset(f, 0, sizeof(f)); memset(s, 0, sizeof(s)); memset(cost, 0, sizeof(cost)); memset(ni, 0, sizeof(ni)); for(i=1; i<=n; i++) { scanf("%d%d%d", &num, &ni[i], &cost[i]); M[num]=i; } scanf("%d", &m); //优惠政策数 for(j=1; j<=m; j++) { scanf("%d", &mm); //涉及的商品数量 for(i=1; i<=mm; i++) { scanf("%d%d", &c, &k); s[j][M[c]]=k; } scanf("%d", &s[j][0]); } for(a1=0; a1<=ni[1]; a1++) for(a2=0; a2<=ni[2]; a2++) for(a3=0; a3<=ni[3]; a3++) for(a4=0; a4<=ni[4]; a4++) for(a5=0; a5<=ni[5]; a5++) { f[a1][a2][a3][a4][a5]=a1*cost[1]+a2*cost[2]+a3*cost[3]+a4*cost[4]+a5*cost[5]; } for(a1=0; a1<=ni[1]; a1++) for(a2=0; a2<=ni[2]; a2++) for(a3=0; a3<=ni[3]; a3++) for(a4=0; a4<=ni[4]; a4++) for(a5=0; a5<=ni[5]; a5++) { for(i=1; i<=m; i++) { if(a1-s[i][1]>=0&&a2-s[i][2]>=0&&a3-s[i][3]>=0&&a4-s[i][4]>=0&&a5-s[i][5]>=0) f[a1][a2][a3][a4][a5]=min(f[a1][a2][a3][a4][a5], f[a1-s[i][1]][a2-s[i][2]][a3-s[i][3]][a4-s[i][4]][a5-s[i][5]]+s[i][0]); } } printf("%d\n", f[ni[1]][ni[2]][ni[3]][ni[4]][ni[5]]); } return 0;}
转载于:https://www.cnblogs.com/Hilda/archive/2013/03/02/2939704.html
View Code