USACO 3.3 Shopping Offers(商店购物)
teafrogsf
2017-12-10 08:16:08
讲道理这种魔性的题目我是拒绝的······要不是有题解我真的不知道写······
当然完全背包的原理还是比较健康的，所以大概还是能理解的吧。
不会讲，贴码子。
```cpp
#include<cstdio>
#include<cstdlib>
#include<iostream>
#define f(i,a,b) for(register int i=a;i<=b;++i)
int n,m,cnt,f[7][7][7][7][7],c[10010],id[1210],v[110][10010],w[10010],tar[10010];
int main()
{
int cc,k,r;
scanf("%d",&m);
f(i,1,m)
{
scanf("%d",&n);
f(j,1,n)
{
scanf("%d%d",&cc,&k);
if(!id[cc])id[cc]=++cnt;
v[i][id[cc]]=k;
}scanf("%d",&w[i]);
}
scanf("%d",&n);
f(i,1,n)
{
scanf("%d%d%d",&cc,&k,&r);
if(!id[cc])id[cc]=++cnt;
c[id[cc]]=r,tar[id[cc]]=k;
}
f(i,0,tar[1])
f(j,0,tar[2])
f(ii,0,tar[3])
f(jj,0,tar[4])
f(ij,0,tar[5])
{
f[i][j][ii][jj][ij]=i*c[1]+j*c[2]+ii*c[3]+jj*c[4]+ij*c[5];
f(ji,1,m)
{
//printf("a=%d %d %d %d %d\n",i,j,ii,jj,ij);
//printf("b=%d %d %d %d %d ",i-v[ji][1],j-v[ji][2],ii-v[ji][3],jj-v[ji][4],ij-v[ji][5]);
//printf("%d\n",f[i-v[ji][1]][j-v[ji][2]][ii-v[ji][3]][jj-v[ji][4]][ij-v[ji][5]]);
if(i-v[ji][1]>=0&&j-v[ji][2]>=0&&ii-v[ji][3]>=0&&jj-v[ji][4]>=0&&ij-v[ji][5]>=0)
f[i][j][ii][jj][ij]=std::min(f[i][j][ii][jj][ij],f[i-v[ji][1]][j-v[ji][2]][ii-v[ji][3]][jj-v[ji][4]][ij-v[ji][5]]+w[ji]);
}
}
printf("%d\n",f[tar[1]][tar[2]][tar[3]][tar[4]][tar[5]]);
}
```