ZOJ 1639 Hang Up the System

题目链接~~>

做题感悟：这题其实用深搜+状态压缩也可以，说不定更快。

解题思路：

                把不可以同时运行，的位于一组中的压缩成二进制这样标记一下（表示不可以计算价值），然后枚举每一种状态如果不合法就标记一下，最后在枚举一下每一种状态，记录合法状态的最优解。

代码：

  

   

    

     

    
    

     

      #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 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/38350497