首页 > 编程学习 > AtCoder Beginner Contest 215 E(DP + 二进制枚举)

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

发布时间:2022/11/6 5:25:17

E - Chain Contestant

E - Chain Contestant

题意

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

思路

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

代码

#include <iostream>
#include <algorithm>
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;
}
Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式