五維DP，聽着挺多的，貌似就是挺裸的dp，
最近貌似做簡單的DP挺順手。。1A
dp[i][j][e][o][g] = min(dp[i][j][e][o][g],dp[i-i1][j-i2][e-i3][o-i4][g-i5]+p[q]) i1,i2...為滿足給出的商品數量的值 p[q]為選用目前優惠方案的價格。
1 /*
2 ID: shangca2
3 LANG: C++
4 TASK: shopping
5 */
6 #include <iostream>
7 #include<cstdio>
8 #include<cstring>
9 #include<algorithm>
10 #include<stdlib.h>
11 using namespace std;
12 #define INF 0xfffffff
13 int dp[6][6][6][6][6];
14 struct node
15 {
16 int c[6],k[6],p,n;
17 }pp[110];
18 int c[6],k[6],p[6];
19 int main()
20 {
21 freopen("shopping.in","r",stdin);
22 freopen("shopping.out","w",stdout);
23 int i,j,s,b,e,o,g,q,a;
24 for(i =0 ; i <= 5 ; i++)
25 for(j = 0 ; j <= 5 ; j++)
26 for(e = 0 ; e <= 5 ; e++)
27 for(o = 0 ; o <= 5 ; o++)
28 for(g = 0 ; g <= 5 ; g++)
29 dp[i][j][e][o][g] = INF;
30 cin>>s;
31 for(i = 1; i <= s ; i++)
32 {
33 cin>>pp[i].n;
34 for(j = 1; j <= pp[i].n ; j++)
35 cin>>pp[i].c[j]>>pp[i].k[j];
36 cin>>pp[i].p;
37 }
38 cin>>b;
39 for(i = 1; i <= b ;i++)
40 cin>>c[i]>>k[i]>>p[i];
41 for(i = 0 ;i <= k[1] ; i++)
42 for(j = 0; j <= k[2] ; j++)
43 for(e = 0; e <= k[3] ; e++)
44 for(o = 0 ; o <= k[4] ;o++)
45 for(g = 0 ; g <= k[5] ; g++)
46 {
47 dp[i][j][e][o][g] = i*p[1]+j*p[2]+e*p[3]+o*p[4]+g*p[5];
48 for(q = 1; q <= s ; q++)
49 {
50 int i1=0,i2=0,i3=0,i4=0,i5=0;
51 for(a = 1; a <= pp[q].n ;a++)
52 {
53 if(pp[q].c[a]==c[1])
54 i1 = pp[q].k[a];
55 else if(pp[q].c[a]==c[2])
56 i2 = pp[q].k[a];
57 else if(pp[q].c[a]==c[3])
58 i3 = pp[q].k[a];
59 else if(pp[q].c[a]==c[4])
60 i4 = pp[q].k[a];
61 else
62 i5 = pp[q].k[a];
63 }
64 if(i-i1>=0&&j-i2>=0&&e-i3>=0&&o-i4>=0&&g-i5>=0)
65 {
66 dp[i][j][e][o][g] = min(dp[i][j][e][o][g],dp[i-i1][j-i2][e-i3][o-i4][g-i5]+pp[q].p);
67 }
68 }
69 }
70 cout<<dp[k[1]][k[2]][k[3]][k[4]][k[5]]<<endl;
71 return 0;
72 } View Code