题目传送门：

　　这道题我用dp做，把每一种优惠方案当作都有5件物品，没有的物品记为0，但写的很乱，所以直接看dp那里就好了

　　

 

1 /* 2 ID:abc31261 3 LANG:C++ 4 TASK:shopping 5 */ 6  7 #include
     
       8 #include
      
        9 #include
       
        10 using namespace std;11 const int maxn=111,maxm=10;12 int a[maxm],n[maxm],c[maxn][maxm],f[maxm][maxm][maxm][maxm][maxm],k[maxn][maxm],p1[maxn],yuan[maxn]; // yuan数组表示原价 13 int main()14 {15     int i,j,l,p,q,i1,i2,s,m;16     freopen("shopping.in","r",stdin);17     freopen("shopping.out","w",stdout);18     scanf("%d",&s);19     memset(f,0x7f,sizeof(f));20     memset(k,0,sizeof(k));21     memset(a,0,sizeof(a));22     f[0][0][0][0][0]=0;23     for (i=1;i<=s;i++)24     {25         scanf("%d",&n[i]);26         for (j=1;j<=n[i];j++)scanf("%d%d",&c[i][j],&k[i][j]);27         scanf("%d",&p1[i]);28     }29     scanf("%d",&m);30     for (i=1;i<=m;i++)31     {32         scanf("%d%d%d",&j,&a[i],&yuan[i]);33         for (l=1;l<=s;l++)34             for (p=1;p<=n[l];p++)35                 if (c[l][p]==j)36                 {37                    swap(c[l][p],c[l][i]);38                    swap(k[l][p],k[l][i]);39                 }40     }41     for (i=0;i<=a[1];i++)42         for (j=0;j<=a[2];j++)43             for (p=0;p<=a[3];p++)44                 for (q=0;q<=a[4];q++)45                     for (l=0;l<=a[5];l++)46                     {47                         if (i>0)f[i][j][p][q][l]=min(f[i][j][p][q][l],f[i-1][j][p][q][l]+yuan[1]);    // dp方程 48                         if (j>0)f[i][j][p][q][l]=min(f[i][j][p][q][l],f[i][j-1][p][q][l]+yuan[2]);49                         if (p>0)f[i][j][p][q][l]=min(f[i][j][p][q][l],f[i][j][p-1][q][l]+yuan[3]);50                         if (q>0)f[i][j][p][q][l]=min(f[i][j][p][q][l],f[i][j][p][q-1][l]+yuan[4]);51                         if (l>0)f[i][j][p][q][l]=min(f[i][j][p][q][l],f[i][j][p][q][l-1]+yuan[5]);52                         for (i1=1;i1<=s;i1++)                                                         //枚举所有优惠方案 53                             if (i>=k[i1][1] && j>=k[i1][2] && p>=k[i1][3] && q>=k[i1][4] && l>=k[i1][5])54                                f[i][j][p][q][l]=min(f[i][j][p][q][l],55                                                     f[i-k[i1][1]][j-k[i1][2]][p-k[i1][3]][q-k[i1][4]][l-k[i1][5]]+p1[i1]);56                     }57     cout<
        
         <