题解 | #牛客推荐系统开发之静态特征获取#

从第一个人开始考虑他所有的棋子，如果他去了这颗棋子那么剩下的人就不能再取，于是修改剩下的人的该类棋子数为零，然后递归至第二个人，递归结束后再把棋子状态改回来。

这样dfs显然会超时，于是我们可以考虑到第三个人时及时刹车。

此时只剩下两个人，只要知道他们各自的棋子总数和重复的棋子数就行了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<string>
#include<map>
#define debug cout<<"**************"<<endl;
using namespace std;
const int mod=1e9+7;
const int maxn=1e6+10;
#define int unsigned long long
int t,n;
int mp[5][5010],qp[5][5010];    
        //开始的时候数组竟然开小了 
int ff(int x,int y,int z,int w)
{
    int ans=0;
    if(x==3){
      return z*y-w;    
    }
    for(int j=1;j<=n;j++)
        if(qp[x][j]==1){
           int t1=y,t2=z,t3=w;
           int e=qp[3][j],f=qp[4][j];
           if(qp[3][j])
               t1=y-1;
           if(qp[4][j])
               t2=z-1;
           for(int k=x+1;k<5;k++){
                  qp[k][j]=0;
           }
           if(e==f&&e==1)
               t3--;
           ans=ans+ff(x+1,t1,t2,t3);
           for(int k=x+1;k<5;k++){
                  qp[k][j]=mp[k][j];
           } 
        }
    return ans; 
} 

signed main(){
    cin>>n;
    for(int i=1;i<=4;i++){
       char str[5100];
       cin>>str;
       for(int j=1;j<=n;j++){
             qp[i][j]=mp[i][j]=str[j-1]-'0';
       }    
    }
    int x,y,z,w;
    x=y=z=w=0;
    x=1;
    for(int i=1;i<=n;i++){
        if(mp[3][i])
        y++;
        if(mp[4][i])
        z++;
        if(mp[3][i]&&mp[4][i])
        w++;
    }
    cout<<ff(x,y,z,w)<<endl;
    return 0;
}