牛客练习赛84 C 牛客推荐系统开发之选飞行棋子

首先这题题型很DP，然后容易想到DP状态f[i][j]为前i个人用前j种棋子的方案数。
后来感觉状态转移不太好写(本人太菜)，就把第一维改成了四个人有无使用棋子的状态压缩，状态转移就很显然了。
这里我用的是刷表法：
f[k][j+1] += f[i][j], 当且仅当：
1. 在二进制下，i为k的真子集，且仅有一个数位不同(令该位置为p，则k=i|1<<p)。
2. s[p][j+1] = '1'。
f[i][j+1] += f[i][j], 正常的转移。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int MAXN = 5e3 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
#define For(i, a, b) for (int i = (int)(a); i <= (int)(b); i++)
#define Rep(i, a, b) for (int i = (int)(a); i >= (int)(b); i--)
#define DEBUG(x) cout << (x) << '\n'
#define fi first
#define se second

int n;
char a[4][MAXN];
ll f[20][MAXN];
inline void run() {
  cin >> n;
  For(i, 0, 3) cin >> a[i] + 1;
  f[0][0] = 1; //初始化
  For(j, 0, n) For(s, 0, 15) {
    For(i, 0, 3)
      if(!(s&1<<i) && a[i][j+1]&1) 
        f[s|1<<i][j+1] += f[s][j];   //第一种转移
    f[s][j+1] += f[s][j];            //第二种转移
  } 
  DEBUG(f[15][n]);                   //15的二进制为1111，表示四个人都用了棋子
}
int main() {
#ifdef Irene
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif // Irene
  ios_base::sync_with_stdio(false);
  cin.tie(0), cin.tie(0);

  // int T; for(cin >> T; T--;)
  run(); return 0;
}