10817 - Headmaster's Headache（状态压缩）

题目链接~~>

做题感悟：这题调试了天才AC掉，感觉自己处理字符串太麻烦了，检查了n遍，最后实在是找不出错误了就把代码的变量规范化了一下就AC了。

解题思路：

                  首先，用 s*2 位数标记状态：前s位表示对应工作是否已经有一个教师在教了，后s 位表示对应工作是否有两个教师在教课，大于两个就不必要记录，这样最多有 16 位标记数组完全开的下。然后就是类似背包滚动数组的做法，依次选择每个教师，并不断更新最优解，这里状态循环的时候要从大到小循环，因为如果从小到大就有可能重复使用一个教师（类似01背包的滚动数组）。

代码：

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<ctime>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<stack>
     
    
   

    

     

    
    

     

      #include<cstring>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const int INF = 1000000000 ;
     
    
   

    

     

    
    

     

      const int MY = 100 + 10 ;
     
    
   

    

     

    
    

     

      const int MX = (1<<16) + 10 ;
     
    
   

    

     

    
    

     

      char s[MY] ;
     
    
   

    

     

    
    

     

      int n ,nx ,m ,Key ,sum ,n2 ;
     
    
   

    

     

    
    

     

      int dp[MX] ,num[MY] ,a[MY] ,w[MY] ;
     
    
   

    

     

    
    

     

      void solveA(char *s) // 处理字符串
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 bool flag = true ;
     
    
   

    

     

    
    

     
 int len = strlen(s) ,st = 0 ,end = len ;
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < len ;i++)
     
    
   

    

     

    
    

     
 if((s[i] == ' ' || i == len-1) && st != end)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(i == len-1)
     
    
   

    

     

    
    

     

       end = len ;
     
    
   

    

     

    
    

     
 else   end = i ;
     
    
   

    

     

    
    

     
 int key = 0 ;
     
    
   

    

     

    
    

     
 for(int j = st ;j < end ;j++)
     
    
   

    

     

    
    

     

       key = key * 10 + s[j] - '0' ;
     
    
   

    

     

    
    

     
 if(flag)  { sum += key ; flag = false ; }
     
    
   

    

     

    
    

     
 else num[key-1]++ ;
     
    
   

    

     

    
    

     

       st = i+1 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void solveB(char *s ,int x) // 处理字符串
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 bool flag = true ;
     
    
   

    

     

    
    

     
 int len = strlen(s) ,st = 0 ,end = len ,K = 0 ;
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < len ;i++)
     
    
   

    

     

    
    

     
 if((s[i] == ' ' || i == len-1) && st != end)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(i == len-1)
     
    
   

    

     

    
    

     

       end = len ;
     
    
   

    

     

    
    

     
 else end = i ;
     
    
   

    

     

    
    

     
 int key = 0 ;
     
    
   

    

     

    
    

     
 for(int j = st ;j < end ;j++)
     
    
   

    

     

    
    

     

       key =key * 10 + s[j] - '0' ;
     
    
   

    

     

    
    

     
 if(flag) { flag = false ,w[x] = key ; }
     
    
   

    

     

    
    

     
 else K |= (1<<(key-1)) ;
     
    
   

    

     

    
    

     

       st = i+1 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       a[x] = K ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void input()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       getchar() ;
     
    
   

    

     

    
    

     

       sum = 0 ; n2 = n*2 ;
     
    
   

    

     

    
    

     
 memset(num ,0 ,sizeof(num)) ;
     
    
   

    

     

    
    

     
 memset(a ,0 ,sizeof(a)) ;
     
    
   

    

     

    
    

     
 memset(w ,0 ,sizeof(w)) ;
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < nx ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       gets(s) ;
     
    
   

    

     

    
    

     

       solveA(s) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < m ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       gets(s) ;
     
    
   

    

     

    
    

     

       solveB(s ,i+1) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       Key = 0 ;
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < n ;i++)
     
    
   

    

     

    
    

     
 if(num[i]==1)
     
    
   

    

     

    
    

     

       Key |= (1<<i) ;
     
    
   

    

     

    
    

     
 else if(num[i] > 1)
     
    
   

    

     

    
    

     

       Key = Key |(1<<i) |(1<<(i+n)) ;
     
    
   

    

     

    
    

     
 memset(dp ,-1 ,sizeof(dp)) ;
     
    
   

    

     

    
    

     

       dp[0] = 0 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      bool judge(int S1 ,int S)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int key = 0 ;
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < n ;i++)
     
    
   

    

     

    
    

     
 if((!(S1 &(1<<i)) && (S &(1<<i)))||((S1 &(1<<i)) && !(S &(1<<i))))
     
    
   

    

     

    
    

     

       key |= (1<<i) ;
     
    
   

    

     

    
    

     
 else  if((S1 &(1<<i)) && (S &(1<<i)))
     
    
   

    

     

    
    

     

       key = key |(1<<i) |(1<<(i+n)) ;
     
    
   

    

     

    
    

     

       key = key |S1 |S ;
     
    
   

    

     

    
    

     

       key = key &((1<<n2)-1) ;
     
    
   

    

     

    
    

     
 if(key == (1<<n2)-1)
     
    
   

    

     

    
    

     
 return true ;
     
    
   

    

     

    
    

     
 else return false ;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void DP()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int ans = INF ;
     
    
   

    

     

    
    

     
 if(Key == (1<<n2)-1)  ans = 0 ;
     
    
   

    

     

    
    

     
 for(int i = 1 ;i <= m ;i++)
     
    
   

    

     

    
    

     
 for(int S = (1<<n2)-1 ;S >= 0 ;S--)
     
    
   

    

     

    
    

     
 if(dp[S] != -1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int key = 0 ;
     
    
   

    

     

    
    

     
 for(int j = 0 ;j < n ;j++)
     
    
   

    

     

    
    

     
 if((!(S &(1<<j)) && (a[i] &(1<<j)))||((S &(1<<j)) && !(a[i] &(1<<j))))
     
    
   

    

     

    
    

     

       key |= (1<<j) ;
     
    
   

    

     

    
    

     
 else if((S &(1<<j)) && (a[i] &(1<<j)))
     
    
   

    

     

    
    

     

       key = key |(1<<j) |(1<<(j+n)) ;
     
    
   

    

     

    
    

     

       key |= S ;
     
    
   

    

     

    
    

     

       key &= ((1<<n2)-1) ; // 放止溢出
     
    
   

    

     

    
    

     
 if(dp[key] != -1)
     
    
   

    

     

    
    

     

       dp[key] = min(dp[key] ,dp[S] + w[i]) ;
     
    
   

    

     

    
    

     
 else dp[key] = dp[S] + w[i] ;
     
    
   

    

     

    
    

     
 if(dp[key] != -1 && judge(key ,Key))
     
    
   

    

     

    
    

     

       ans = min(ans ,dp[key]) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 cout<<ans+sum<<endl ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 while(scanf("%d%d%d",&n ,&nx ,&m) ,n)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       input() ;
     
    
   

    

     

    
    

     

       DP() ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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