【CF-GYM】【状压DP】100837F Controlled Tournament

CF-GYM 100837F Controlled Tournament

题目大意

有$N$个人参加比赛，其中你是比赛的组织者，你必须帮助第$M$个人使他获胜。求让比赛轮数最小时的方案数。

分析

看到了这么小的$N$，我们很容易往状压 DP 上想。

考虑状态$f(i,S,d)$表示当前参加的人为$S$，我们想让第$i$个人胜出且经过$d$层的方案数。

转移就枚举$S$的非空子集转移即可。

但这样用循环直接做的话复杂度为$O(3^N\times N^3)$的。

我们发现这样定义无用状态其实非常多的，所以我们就用记忆化搜索来实现这个 DP 以规避无用状态。

参考代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int Maxn = 16;inline int lowbit(int x) {
    return x & (-x);}
inline int bitcount(int x) {
    int ret = 0;while(x) ret++, x -= lowbit(x);return ret;
}
inline int height(int x) {
    int ret = 0;while((1 << ret) < x) ret++;return ret;
}int N, M;
int R[Maxn + 5][Maxn + 5];
int h[Maxn + 5];int f[7][Maxn + 3][(1 << Maxn) + 3];
int DFS(int dep, int win, int s) {
    if(f[dep][win][s] != -1) return f[dep][win][s];if(bitcount(s) == 1) {
    if(s & (1 << (win - 1))) return f[dep][win][s] = 1;else return f[dep][win][s] = 0;}f[dep][win][s] = 0;for(int t = (s - 1) & s; t > 0; t = (t - 1) & s) {
    int s1 = t, s2 = s ^ t;if(!(s1 & (1 << (win - 1)))) continue;if(h[bitcount(s1)] > dep - 1 || h[bitcount(s2)] > dep - 1)continue;int ans1 = DFS(dep - 1, win, s1);int ans2 = 0;for(int i = 1; i <= N; i++)if((s2 & (1 << (i - 1))) && R[win][i])ans2 += DFS(dep - 1, i, s2);f[dep][win][s] += ans1 * ans2;}return f[dep][win][s];
}int main() {
    
//#ifdef LOACL
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
//#endiffreopen("f.in", "r", stdin);freopen("f.out", "w", stdout);scanf("%d %d", &N, &M);for(int i = 1; i <= N; i++)for(int j = 1; j <= N; j++)scanf("%d", &R[i][j]);for(int i = 1; i <= N; i++)h[i] = height(i);memset(f, -1, sizeof f);printf("%d\n", DFS(h[N], M, (1 << N) - 1));return 0;
}