#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i(j);i<=k;++i)
#define drp(i,j,k) for(register int i(j);i>=k;--i)
using namespace std;
const int inf=0xfffffff;

template<typename T>
inline void read(T &x)
{
	x=0;
	int w=0;
	char register ch=getchar();
	while(ch>'9'||ch<'0')
		{
			w|=ch=='-';
			ch=getchar();
		}
	while(ch>='0'&&ch<='9')
		{
			x=(x*10)+(ch&15);
			ch=getchar();
		}
	w?x=~(x-1):x;
}
template<typename T>
inline void out(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x==0)
		{
			putchar('0');
			putchar('\n');
			return ;
		}
	char c[50];
	int num(0);
	while(x)
		{
			c[++num]=x%10+48;
			x/=10;
		}
	while(num) putchar(c[num--]);
	putchar('\n');
}

int n,m;
int maxn;
//int f[(1<<20)];
// n个错误 即 n个1

// f[i]  状态i 修复 的最少时间

//  初始化 f[i]=inf;  f[(1<<n)-1] =0;
// 目标状态    f[0]

int f[(1<<22)];
char BB[107][22],FF[107][22];
int cost[107];
int B1[107],B2[107],F1[107],F2[107];
//包含 B1[i]中的所有，而不包含 B2[i]中的任何   +∈B1    -∈F2[i]
// 修复错误 F1[i] 加入错误 F2[i]   -∈F1    +∈F2
int main()
{
//	freopen("cyrcyr.in","r",stdin);
//	freopen("cyrcyr.out","w",stdout);
//   cout<<(double)(sizeof f) /1024/1024;
	read(n);
	read(m);
	maxn=(1<<n)-1;
	rep(i,0,(1<<21)) f[i]=inf;
	f[maxn]=0;
	rep(i,1,m)
	{
		read(cost[i]);
		scanf("%s",BB[i]);
		rep(j,0,n-1)
		{
			if(BB[i][j]=='+') B1[i]|=(1<<(n-1-j));
			if(BB[i][j]=='-') B2[i]|=(1<<(n-1-j));
		}
		scanf("%s",FF[i]);
		rep(j,0,n-1)
		{
			if(FF[i][j]=='-') F1[i]|=(1<<(n-1-j));
			if(FF[i][j]=='+') F2[i]|=(1<<(n-1-j));
		}
//		cout<<B1[i]<<' '<<B2[i]<<' '<<F1[i]<<' '<<F2[i]<<endl;
//		system("pause");
	}

	drp(i,maxn,1)//枚举错误状态;
	{
		rep(j,1,m)
		{
			bool flag(1);
			rep(k,0,n-1)
			{
				int t=(i&(1<<(k))); //取出i第k-1位状态 
				int b1=( B1[j]&(1<<(k))   );
				int b2=( B2[j]&(1<<(k))   );
				if(    (  ( (!t)&&b1) )  ||   ( (t&&b2)   )   )
				{
					flag=0;
					break;
				}
			}
			if(!flag) continue;
			int now=i;
			rep(k,0,n-1)
			{
			  if( F1[j]&(1<<k)  )
			  {
			  	now=  now&( ~(1<<k) );
			  }
			  if(F2[j]&(1<<k) )	
			  {
			  	now=now|(1<<k);
			  }
			}
			f[now]=min(f[now],f[i]+cost[j]);
		}
	}
	if(f[0]>=inf) cout<<0;
	else
	out(f[0]);
	return 0;
//	cout<<f[0];
}

用了很久写出的状压 发现两WA一TLE。。。。

有后效性的dp很少见啊。。为什么大家都想到图论。