给定物品种类数n(0到5),接下来n行每行3个数商品编码c_i(1到999),需要购买的数量k_i(1到5),单价p_i(1到999).
然后给定m(0到99)种优惠,接下来m行,每行第一个数字q表示这种优惠需要购买的物品种类数,接着q个数对(c,k)表示编码为c的商品买k个,每行最后一个数字表示买这些物品组合的优惠价.
输出购买所需物品的最少价格.
考虑dp
状态表示:dp[n1][n2][n3][n4][n5]" role="presentation">dp[n1][n2][n3][n4][n5]表示第1,2,3,4,5种物品购买数量分别为n_1,n_2,n_3,n_4,n_5的最小价格.
边界状态:dp[0][0][0][0][0]=0" role="presentation">dp[0][0][0][0][0]=0
状态转移:设p_i为第i种优惠,将单价也视为一种优惠.
dp[n1][n2][n3][n4][n5]=mini=1m{dp[n1−pi1][n2−pi2][n3−pi3][n4−pi4][n5−pi5]}" role="presentation">dp[n1][n2][n3][n4][n5]=mini=1m{dp[n1−pi1][n2−pi2][n3−pi3][n4−pi4][n5−pi5]}
记忆化搜索.
真是神奇,记得有时间补了电梯那道题,记忆化搜索之王.
/* LittleFall : Hello! */ #include <bits/stdc++.h> using namespace std;typedef long long ll; inline int read();inline void write(int x); const int M = 5; int mp[M], need[M]; //商品编码映射,所需商品个数 int dp[M][M][M][M][M]; struct Sale { int num[M]; int price = 0; } sale[M]; //优惠 int sales; //优惠数 int mymin(int a, int b){return a == -1 ? b : min(a, b);} int search() { int &ans = dp[need[0]][need[1]][need[2]][need[3]][need[4]]; if(ans != -1) return ans; for(int i = 0; i < sales; i++) { int flag = 1; for(int j = 0; j < M; j++) if(need[j] < sale[i].num[j]) flag = 0, j = M; if(!flag) continue; for(int j = 0; j < M; j++) need[j] -= sale[i].num[j]; ans = mymin(ans, search() + sale[i].price); for(int j = 0; j < M; j++) need[j] += sale[i].num[j]; } return ans; } int main(void) { freopen("3-14.txt", "r", stdin); int n = read(); for(sales = 0; sales < n; sales++) { mp[read()] = sales; need[sales] = read(); sale[sales].num[sales] = 1; sale[sales].price = read(); } int m = read(); for(; sales < n + m; sales++) { int k = read(); while(k--) { int id = mp[read()]; sale[sales].num[id] = read(); } sale[sales].price = read(); } memset(dp, -1, sizeof(dp)); dp[0][0][0][0][0] = 0; write(search()); return 0; } inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void write(int x) { if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); }
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
