放假打题 sufu
看完题我是懵比的 这.... emmmmm 瓜想了半个小时之后我选择狗带 然后点开链接 状压+dp！！！！哦！！！！！！巧妙！！！！
就先把目标状态还有各个优惠的状态处理好 然后就是一个完全背包处理用优惠
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int S=100+5,N=10,P=10000+5,C=1000+5; 4 int sale[S],sp[S],sta=0,f[50000],pri[N],cnt,s,b,c,k,p; 5 int base[N],cd[50000]; 6 7 template<class t>void rd(t &x) 8 { 9 x=0;int w=0;char ch=0; 10 while(!isdigit(ch)) w|=ch=='-',ch=getchar(); 11 while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 12 x=w?-x:x; 13 } 14 15 bool jud(int st,int x[N]) 16 { 17 int cur=0; 18 while(st) 19 { 20 if((st%6)>x[++cur]) return 0; 21 st/=6; 22 } 23 return 1; 24 } 25 26 int main() 27 { 28 memset(cd,0,sizeof(cd)); 29 memset(sale,0,sizeof(sale)); 30 base[1]=1; 31 for(int i=2;i<=6;++i) base[i]=base[i-1]*6; 32 rd(s); 33 for(int i=1;i<=s;++i) 34 { 35 int n;rd(n); 36 for(int j=1;j<=n;++j) 37 { 38 rd(c),rd(k); 39 if(!cd[c]) cd[c]=++cnt; 40 sale[i]+=base[cd[c]]*k; 41 } 42 rd(sp[i]); 43 } 44 rd(b); 45 for(int i=1;i<=b;++i) 46 { 47 rd(c),rd(k),rd(p); 48 if(!cd[c]) cd[c]=++cnt; 49 sta+=base[cd[c]]*k,pri[cd[c]]=p; 50 } 51 for(int ss=1;ss<=sta;++ss) 52 { 53 int pro[N],nw=ss,cur=0; 54 while(nw) pro[++cur]=nw%6,nw/=6; 55 for(int i=1;i<=cur;++i) f[ss]+=pro[i]*pri[i]; 56 for(int i=1;i<=s;++i) 57 if(ss>=sale[i]&&jud(sale[i],pro)) 58 f[ss]=min(f[ss],f[ss-sale[i]]+sp[i]); 59 } 60 printf("%d",f[sta]); 61 return 0; 62 }