记录编号	583148	评测结果	AAAAAAAAAA
题目名称	[CTSC 1999] BUG修复	最终得分	100
用户昵称	宇战	是否通过	通过
代码语言	C++	运行时间	0.252 s
提交时间	2023-10-05 12:16:59	内存使用	2.30 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=233;
int n,m,ans=0x3f3f3f3f;
map<unsigned long long,bool>mm;
struct node{
    int time;
    int o1[30],o2[30];
}a[110];
int q[25];
bool finish(int p[25]){
    for(int i=1;i<=n;i++){
        if(p[i]!=0){
            return 0;
        }
    }
    return 1;
}
int fff=0;
unsigned long long hashs(int ooo[25]){
    unsigned long long ans=0,ooop=1;
    for(int i=1;i<=n;i++){
        ans+=ooo[i]*ooop;
        ooop*=N;
    }
    return ans;
}
void dfs(int s,int ooo[25]){
     int oo[25]={0};
     if(s>=ans)return ; 
     for(int i=1;i<=n;i++){
         oo[i]=ooo[i];
     }
     if(finish(oo)){
         ans=min(ans,s);
         return;
     }
     for(int i=1;i<=m;i++){
         bool k=0;
         for(int j=1;j<=n;j++){
             if(a[i].o1[j]==1&&oo[j]!=0){
                 k=1;
                 break;
             } 
             if(a[i].o1[j]==2&&oo[j]!=1){
                 k=1;
                 break;
             }
         }
         if(!k){
             for(int j=1;j<=n;j++){
                 if(a[i].o2[j]==1){
                     oo[j]=0;
                 }
                 if(a[i].o2[j]==2){
                     oo[j]=1;
                 }
             }
             if(mm[hashs(oo)]==0){
                 mm[hashs(oo)]=1;
                 dfs(s+a[i].time,oo);
                 mm[hashs(oo)]=0;
                 for(int i=1;i<=n;i++){
                         oo[i]=ooo[i];
                 }
             }else{
                 for(int i=1;i<=n;i++){
                         oo[i]=ooo[i];
                 }
                 continue;
             } 
             
         }
     }
}
int main(){
    freopen("bug.in","r",stdin);
    freopen("bug.out","w",stdout);
      cin>>n>>m;
      for(int i=1;i<=25;i++){
          q[i]=1;
      } 
      for(int i=1;i<=m;i++){
          cin>>a[i].time;
          for(int j=1;j<=n;j++){
              char op;
              cin>>op;
              if(op=='-'){
                  a[i].o1[j]=1;
              }else if(op=='+'){
                  a[i].o1[j]=2;
              }
          } 
          for(int j=1;j<=n;j++){
              char op;
              cin>>op;
              if(op=='-'){
                  a[i].o2[j]=1;
              }else if(op=='+'){
                  a[i].o2[j]=2;
              }
          }          
      }
      mm[hashs(q)]=1;
      dfs(0,q); 
      if(ans==0x3f3f3f3f){
      	cout<<0;
      	return 0;
	  }
      cout<<ans;
      return 0;
}