This post is written in Chinese. Please consider using Google Translate

五维的动态规划 状态设置：

F[a1][a2][a3][a4][a5]为买a1件物品1,a2件物品2,a3件物品3,a4件物品4,a5件物品5时，所需的最少价格

边界条件：

F[0][0][0][0][0]=0;

状态转移方程：

F[a1][a2][a3][a4][a5]=min{F[ a1-P[i][1] ][ a2-P[i][2] ][ a3-P[i][3] ][ a4-P[i][4] ][ a5-P[i][5] ]+P[i][0])} 其中i=1..s+b; 且 ak-p[i][k]>=0

注意一些特殊数据，如

0 0

之类的

USER: CmYkRgB CmYkRgB [cmykrgb1]
TASK: shopping
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 2880 KB]
   Test 2: TEST OK [0.000 secs, 2884 KB]
   Test 3: TEST OK [0.000 secs, 2884 KB]
   Test 4: TEST OK [0.000 secs, 2880 KB]
   Test 5: TEST OK [0.000 secs, 2880 KB]
   Test 6: TEST OK [0.000 secs, 2884 KB]
   Test 7: TEST OK [0.000 secs, 2880 KB]
   Test 8: TEST OK [0.000 secs, 2884 KB]
   Test 9: TEST OK [0.000 secs, 2884 KB]
   Test 10: TEST OK [0.022 secs, 2884 KB]
   Test 11: TEST OK [0.032 secs, 2880 KB]
   Test 12: TEST OK [0.032 secs, 2884 KB]

All tests OK.

记忆化的递归实现

/*
ID: cmykrgb1
PROG: shopping
LANG: C++
*/
#include <iostream>
#include <fstream>
using namespace std;
ifstream fi("shopping.in");
ofstream fo("shopping.out");
long P[105][6];
long buy[6];
long n,ans;
long c_n[1000];
long F[6][6][6][6][6];
long ori;

void init()
{
    long i,j,m,tp=0,c,k,s,b;
    fi >> s;
    for (i=1;i<=s;i++)
    {
        fi >>m;
        for (j=1;j<=m;j++)
        {
            fi>> c >> k;
            if (c_n[c]==0) c_n[c]=++tp;
            P[i][ c_n[c] ]=k;
        }
        fi >> P[i][0];
    }
    fi >> b;
    for (i=1;i<=b;i++)
    {
        fi>> c >> k >> P[s+i][0];
        if (c_n[c]==0) c_n[c]=++tp;
        P[s+i][ c_n[c] ]=1;
        buy[c_n[c]]=k;
    }
    n=s+b;
    memset(F,0xF,sizeof(F));
    ori=F[0][0][0][0][0];
    F[0][0][0][0][0]=0;
}

void print()
{
    fo << ans <<endl;
    fi.close();
    fo.close();
}

inline long min(long a,long b)
{
    return a<b?a:b;
}

long get(long a1,long a2,long a3,long a4,long a5)
{
    if (F[a1][a2][a3][a4][a5]!=ori)
        return F[a1][a2][a3][a4][a5];
    long i;
    long w1,w2,w3,w4,w5,pmin=ori;
    for (i=1;i<=n;i++)
    {
        w1=a1-P[i][1];w2=a2-P[i][2];w3=a3-P[i][3];w4=a4-P[i][4];w5=a5-P[i][5];
        if (w1<0||w2<0||w3<0||w4<0||w5<0) continue;
        if (F[w1][w2][w3][w4][w5]==ori)
            F[w1][w2][w3][w4][w5]=get(w1,w2,w3,w4,w5);
        pmin=min(pmin,F[w1][w2][w3][w4][w5]+P[i][0]);
    }
    return pmin;
}

int main()
{
    init();
    ans=get(buy[1],buy[2],buy[3],buy[4],buy[5]);
    print();
    return 0;
}