题目：

状态压缩的DP，dp[i][st]表示状态为st考虑后面i个人所有人最小花费，

因为每个科目有三种状态，可以用一个三进制数表示，

状态不是很多，所以可以把预先把每个数的三进制预处理出来，

决策为选和不选。

#include
     
      using namespace std;const int maxs = 8;const int MAXSTA = 6561+5;const int maxn = 101;int base[maxs+1],trp[MAXSTA][maxs+1];int dp[maxn][MAXSTA];int tch[maxn],cost[maxn],sa;int s,m,n;const int INF = 0x3fffffff;void preDeal(){    base[0] = 1;    for(int i = 1; i <= maxs; i++){        base[i] = 3*base[i-1];    }    for(int i = 1; i < MAXSTA; i++){        int x = i, cnt = 0;        while(x){            trp[i][cnt++] = x%3;            x /= 3;        }    }}int dfs(int i,int st){    if(i == n) return st == sa? 0:INF;    int &ans = dp[i][st];    if(~ans) return ans;    ans = dfs(i+1,st);    //int nst = st;    for(int j = 0; j < s; j++){        if(trp[tch[i]][j] && trp[st][j] != 2){            st += base[j];        }    }    ans = min(ans,dfs(i+1,st)+cost[i]);    return ans;}int work(){    sa = base[s]-1;    int st = 0,sum = 0;    for(int i = 0; i < m; i++){        int c; scanf("%d",&c);        sum += c;        while(getchar()!='\n'){            int sub = getchar()-'1';            int t = trp[st][sub] ;            if(t != 2){                st += base[sub];            }        }    }    for(int i = 0; i < n; i++){        scanf("%d",cost+i);        tch[i] = 0;        while(getchar()!='\n'){            tch[i] += base[getchar()-'1'];        }    }    memset(dp,-1,sizeof(dp));    return sum + dfs(0,st);}int main(){    //freopen("in.txt","r",stdin);    preDeal();    while(scanf("%d%d%d",&s,&m,&n),s){        printf("%d\n",work());    }    return 0;}