标签 ： 状态压缩dp

---

题目链接

分析

• 用dp[i][j]来表示已经有i个人成功就坐,且坐下的状态为j的二进制.
• 转移的时候枚举第i个人卡片上的数字

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef long long ll;ll dp[15][1<<16];vector
           
             v[20];ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}int main(){ int t; scanf("%d", &t); for(int i = 0; i < (1<<15); ++i){ int j=i,cnt=0; while(j) j-=(j&-j),cnt++; v[cnt].push_back(i); } while(t--){ int n,k; scanf("%d%d", &n,&k); memset(dp,0,sizeof dp); dp[0][0]=1; for(int i = 0; i <= n; ++i){ for(int j = 0; j < (1<
            
             >p)%2==0){ dp[i+1][j|(1<