做题感悟：这题其实用深搜+状态压缩也可以，说不定更快。
解题思路：
把不可以同时运行，的位于一组中的压缩成二进制这样标记一下（表示不可以计算价值），然后枚举每一种状态如果不合法就标记一下，最后在枚举一下每一种状态，记录合法状态的最优解。
代码：
#include<stdio.h>
#include<map>
#include<queue>
#include<cmath>
#include<string.h>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stdlib.h>
#define INT unsigned long long int
using namespace std ;
const int MY = 100 + 10 ;
const int MX = 2000 + 10 ;
int n,mx ;
int w[MX] ;
bool vis[1<<16] ;
map<string,int>m ;
void solve(char *s1,int num)// 分解字符串
{
string sx="" ;
int key=0 ;
int len=strlen(s1),st=0,ed ;
for(int i=0 ;i<len ;i++)
{
if(s1[i]==' '||i==len-1)
{
sx="" ;
if(i==len-1) ed=len ;
else ed=i ;
for(int j=st ;j<ed ;j++)
sx+=s1[j] ;
key=key|(1<<m[sx]) ;
st=i+1 ;
}
}
vis[key]=true ;
}
void DP()
{
int best=0 ;
for(int S=0 ;S<(1<<n) ;S++) // 枚举每一种状态标记不合法状态
for(int i=0 ;i<n ;i++)
if((S&(1<<i))&&vis[S^(1<<i)])
{
vis[S]=true ;
break ;
}
for(int S=0 ;S<(1<<n) ;S++) // 取合法状态记录最优解
{
if(vis[S]) continue ;
int ans=0 ;
for(int i=0 ;i<n ;i++)
if(S&(1<<i))
ans+=w[i] ;
best = max(ans,best) ;
}
cout<<best<<endl ;
}
void input()
{
string s="" ;
char s1[MX] ;
m.clear() ;
memset(vis,false,sizeof(vis)) ;
for(int i=0 ;i<n ;i++)
{
cin>>s>>w[i] ;
m[s]=i ;
}
scanf("%d",&mx) ;
getchar() ;
for(int i=0 ;i<mx ;i++)
{
gets(s1) ;
solve(s1,i) ;
}
}
int main()
{
int cse=1 ;
while(cin>>n,n)
{
input() ;
cout<<"System "<<cse++<<": " ;
DP() ;
}
return 0 ;
}