记录编号	583151	评测结果	AAAAAAAAAA
题目名称	[CTSC 1999] BUG修复	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.291 s
提交时间	2023-10-05 14:34:35	内存使用	2.88 MiB

#include <bits/stdc++.h> 
using namespace std;
typedef unsigned long long ll;
const int N = 110,p = 1e9+10;
int n,m,ans = INT_MAX;
int b[31];
map<ll,bool>q;
struct made{
    int m;
    int la[31],ne[31];
}a[N]; 
ll hash_(int s[31]){
    ll su = 0,p1 = 1;
    for(int i = 1;i <= n;i++){
        su += p1 * s[i];
        p1 *= p;
    }
    return su;
}
bool can(int x[31],int y[31]){
    for(int i = 1;i <= n;i++)
        if(x[i] != y[i] && y[i] != 0)return 0;
    return 1;
}
bool check(int s[31]){
    for(int i = 1;i <= n;i++)
        if(s[i] != 1)return 0;
    return 1;
}
bool use(int x[31],int y[31]){
    bool f = 1;
    for(int i = 1;i <= n;i++){
        if(y[i] == 0)continue;
        if(x[i] < y[i])f = 0;
        else if(x[i] > y[i])return 1;
    }
    return f;
}
void dfs(int x,int u[31]){
    if(x >= ans)return;//剪枝 
    int s[31] = {0};
//    memcpy(s,u,sizeof(s));
    for(int i = 1;i <= n;i++)s[i] = u[i];
    if(check(s)){
        ans = min(ans,x);
        return;
    }
    for(int i = 1;i <= m;i++){
        int f = 0;
        if(can(s,a[i].la) && !can(s,a[i].ne) && q[hash_(s)] == 0 /*use(s,a[i].ne)*/){
            q[hash_(s)] = 1;
            for(int j = 1;j <= n;j++)
                if(a[i].ne[j] != 0)s[j] = a[i].ne[j];
            dfs(x+a[i].m,s);
            for(int i = 1;i <= n;i++)s[i] = u[i];
            q[hash_(s)] = 0;
        }
    }
}
int main(){
    freopen("bug.in","r",stdin);
    freopen("bug.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++)b[i] = 2;
    for(int i = 1;i <= m;i++){
        char c1[21],c2[21];
        scanf("%d%s%s",&a[i].m,c1+1,c2+1);
        for(int j = 1;j <= n;j++){
            if(c1[j] == '0')a[i].la[j] = 0;
            if(c1[j] == '-')a[i].la[j] = 1;
            if(c1[j] == '+')a[i].la[j] = 2;
            if(c2[j] == '0')a[i].ne[j] = 0;
            if(c2[j] == '-')a[i].ne[j] = 1;
            if(c2[j] == '+')a[i].ne[j] = 2;
        }
    }
    dfs(0,b);
    if(ans == INT_MAX)printf("0");
    else printf("%d\n",ans);
    
    return 0;
}