放假打题 sufu

看完题我是懵比的 这....  emmmmm   瓜想了半个小时之后我选择狗带 然后点开链接 状压+dp！！！！哦！！！！！！巧妙！！！！

就先把目标状态还有各个优惠的状态处理好 然后就是一个完全背包处理用优惠

1 #include
     
       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
      
       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 }