AtCoder Beginner Contest 215 E(DP + 二进制枚举)

E - Chain Contestant

E - Chain Contestant

题意

有$n$场比赛，$m$种比赛，种类最多有$10$种，现要求如果要参加相同种类的比赛只能连续参加，问有多少种参加比赛的方案（第$i$场比赛可以不参加，但至少参加一场比赛）。$n<=1000，m<=10$

思路

考虑DP状态转移，设第$i$场比赛的种类为$s[i]$，第$i$场比赛参加与否取决于之前的比赛，如果之前的比赛参加过$s[i]$的种类，那么这次就不能参加，除非上一次参加的比赛也是$s[i]$，这次可以接着参加。
于是我们需要记录的状态有：上一次参加的比赛种类，之前参加过的所有比赛种类。因为比赛种类较少，可以用二进制来记录，每一个二进制数的数位就代表是否参加过该种类比赛。
定义DP数组$f[i][j][k]$:前$i$场比赛,在二进制下打过$j$中数位为$1$的场次，且最后一场打$k$的方案数。
时间复杂度$O(n\ast 2^m)$
具体实现在代码中，有注释。

代码

#include 
#include 
using namespace std;
#define ll long long
const int N = 1010, mod = 998244353;
int f[N][11][1 << 11];//前i场比赛,在二进制下打过k中数位为1的场次，且最后一场打j的方案数
int main()
{
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    int n;
    string s;
    cin >> n >> s;
    
    for(int i = 1; i <= n; i ++){
        int c = s[i - 1] - 'A'; 
        f[i][c][1 << c] = 1;//初始化第一场比赛
        for(int k = 0; k < 10; k ++){//枚举上一场参加的比赛
            for(int j = 1; j < (1 << 10); j ++){//枚举之前参加的所有比赛

                f[i][k][j] = (f[i][k][j] + f[i - 1][k][j]) % mod; //第i场比赛不打

                if(!(j >> c & 1) || c == k){//第i场比赛打，前提是之前没打过或者之前最后一场打的就是s[i],可以接着打
                    int tmp = j + (1 << c) * (!(j >> c & 1));
                    f[i][c][tmp] = (f[i][c][tmp] + f[i - 1][k][j]) % mod;
                }
            }
        }
    }

    ll ans = 0;
    for(int i = 0; i < 10; i ++){
        for(int j = 1; j < (1 << 10); j ++){
            ans = (ans + f[n][i][j]) % mod;
        }
    }
    cout << ans;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39