星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

USACO 3.3 Shopping Offers(商店购物)

posted on 2017-12-10 08:16:08 | under 题解 |

讲道理这种魔性的题目我是拒绝的······要不是有题解我真的不知道写······

当然完全背包的原理还是比较健康的,所以大概还是能理解的吧。

不会讲,贴码子。

#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]]);
}