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

C题
dp大法好
没考虑太多

• 存储
  代表第 人
  代表第 个棋子

• 开了
  （1-N）表示在前 个棋子里面选
  （0-15）表示四位二进制数，比如“1101”代表一、二、四号选了棋子，三号还没选棋子

至此我们可以推出 比如当

总结下规律，简化代码，可以得到

    dp[i][j]=dp[i-1][j];
    ll t=0,m=j;
    while(m>0){
        if(m%2==1){
            ll p=pow(2,t);
            dp[i][j]+=dp[i-1][j-p]*a[4-t][i];
        }
        t++;m/=2;
    }

附上全部代码

#include<stdio.h>
#include<iostream>
#include <stdlib.h>
#include <time.h>
#include<string.h>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
#define ll long long
#define maxn 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f3f
#define mdd 1000000007
#include <fstream>
using namespace std;
ll i,j,m,n,x,y,z,l,r,t,k,p,pp,num,sum,cnt,flag,minn,maxx,ans,key;
ll a[20][20100],b[200100],mapp[200][200],vis[1010][200],pre[100100],dp[20100][20];
char cc[60],zz;
//double xa[5],ya[5],xb[5],yb[5],ee,ff;
//vector<string>v;
//string a,b;
//map<string,map<string,ll>>mp;
priority_queue<ll,vector<ll>,greater<ll> >s;

struct qq{ll xx,yy,zz,dd;};

bool cmp(qq u,qq v){
    return u.xx<v.xx;
}

void f(ll i,ll j){
    dp[i][j]=dp[i-1][j];
    ll t=0,m=j;
    while(m>0){
        if(m%2==1){
            ll p=pow(2,t);
            dp[i][j]+=dp[i-1][j-p]*a[4-t][i];
        }
        t++;m/=2;
    }
}

int main(){
    scanf("%lld",&n);
    for(i=1;i<=4;i++){
        for(j=1;j<=n;j++)scanf("%1lld",&a[i][j]);
    }
    for(i=0;i<=n;i++)dp[i][0]=1;
    for(i=1;i<=n;i++){
        for(j=1;j<=15;j++){
            f(i,j);
        }
    }
    printf("%lld\n",dp[n][15]);
}

小菜鸡一枚，欢迎纠正~