In a shop each kind of product has a price. For example, the price of a flower is 2 ICU (Informatics Currency Units) and the price of a vase is 5 ICU. In order to attract more customers, the shop introduces some special offers. A special offer consists of one or more product items for a reduced price. Examples: three flowers for 5 ICU instead of 6, or two vases together with one flower for 10 ICU instead of 12. Write a program that calculates the price a customer has to pay for certain items, making optimal use of the special offers. That is, the price should be as low as possible. You are not allowed to add items, even if that would lower the price. For the prices and offers given above, the (lowest) price for three flowers and two vases is 14 ICU: two vases and one flower for the reduced price of 10 ICU and two flowers for the regular price of 4 ICU.
这道题开始想用dp[i][j] 状态压缩来表示的，无奈j的状态太多了。 我们可以从需要购买的物品入手，dp[i][j][k][p][q]五维来表示每一维需要购买的物品数，然后记忆化搜索。 复杂度O(6^5) 填满整个dp数组即可。
#include<iostream> using namespace std; #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<stdlib.h> #include<vector> #include<queue> #include<deque> #include<map> #include<set> #include<time.h> #define pi(x,y) printf("%d%c",(x),(y)); #define pin(x) printf("%d\n",(x)); #define si(x) scanf("%d",&(x)) #define sii(x,y) scanf("%d%d",&(x),&(y)) #define s3(x,y,z) scanf("%d%d%d",&(x),&(y),&(z)) #define rep(x,y,z) for(int (x)=(y);(x)<(z);++(x)) #define dep(x,y,z) for(int (x)=(y)-1;(x)>=(z);--(x)) #define read int TcaseN;scanf("%d",&TcaseN);for(int Tcase=1;Tcase<=TcaseN;++Tcase) #define cls(x,y) memset((x),(y),sizeof((x))); #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) #define max3(value_a,value_b,value_c) max(max(value_a,value_b),value_c) #define min3(value_a,value_b,value_c) min(min(value_a,value_b),value_c) #define GT(x) (x)=clock(); #define fin(x) freopen(x,"r",stdin); #define fout(x) freopen(x,"w",stdout); ///In This You Can Define Long Integer Type #define LONGTYPE long long typedef LONGTYPE LL; typedef unsigned LONGTYPE ULL; const int maxint=((~((unsigned)(0)))>>1); const LL maxll=((~((unsigned LONGTYPE)(0)))>>1); const int inf=0x3f3f3f3f; const double PI=acos(-1.0); const int maxn=1e3+5; struct note{ int x,y,z; }A[5]; int n,m; struct notes{ int a[5],val; notes(){ } notes(int arr[]){ for(int i=0;i<5;++i){ a[i]=arr[i]; } val=arr[5]; } }; vector<notes> B; int dp[6][6][6][6][6]; map<int,int> MP; int dfs(int a,int b,int c,int d,int e){ if(a<0||b<0||c<0||d<0||e<0)return inf; int &ans=dp[a][b][c][d][e]; if(~ans)return ans; ans=a*A[0].z+b*A[1].z+c*A[2].z+d*A[3].z+e*A[4].z; int t=inf; for(int i=0;i<m;++i){ t=min(t,dfs(a-B[i].a[0],b-B[i].a[1],c-B[i].a[2],d-B[i].a[3],e-B[i].a[4])+B[i].val); } return ans=min(ans,t); } int main() { #ifdef tangge clock_t tSTART,tEND,t3; GT(tSTART); #endif // tangge /*Input:*/ while(scanf("%d",&n)==1){ memset(dp,-1,sizeof(dp)); MP.clear(); for(int i=0;i<n;++i){ scanf("%d%d%d",&A[i].x,&A[i].y,&A[i].z); MP[A[i].x]=i; } for(int i=n;i<=4;++i){ A[i].x=A[i].y=A[i].z=0; } scanf("%d",&m); for(int i=0;i<m;++i){ int k;scanf("%d",&k); int L[6]; memset(L,0,sizeof(L)); for(int j=0;j<k;++j){ int t1,t2;scanf("%d%d",&t1,&t2); L[MP[t1]]+=t2; } scanf("%d",&L[5]); B.push_back(notes(L)); } if(!n){ puts("0");continue; } printf("%d\n",dfs(A[0].y,A[1].y,A[2].y,A[3].y,A[4].y)); } #ifdef tangge GT(tEND); printf("%.8lf\n",(tEND-tSTART)/1000.0); #endif // tangge return 0; }