小旭讲解 基础算法系列 – 状态压缩 DP 之 Chain Contestant

视频讲解

代码

// idx 0 1 2 3 4 5
 // S = A A B B A C
 // f[i][u][j]
 // u = {A,C}, {A}
 // A B C
 // 1 0 1
 // not choose S[i]
 //      f[i][u][j] += f[i-1][u][j]
 // choose S[i] = x
 //      连续
 //          j == x(S[i])
 //          f[i][u][j] += f[i-1][u][j]
 //      不连续
 //          v' = x + v
 //          j != x
 //          f[i][v'][x] += f[i-1][v][j]
 //  f[i][W][x] = 1 W 中只包含 x 的情况下
 include
 using namespace std;
 long long f[1024][1024][10];
 define mod 998244353
 int n;
 string S;
 int main() {
     cin>>n;
     cin>>S;
     memset(f, 0, sizeof f);
     for (int i=1;i<=n;++i) {
         auto x = S[i-1] - 'A';
         // not choose S[i]
         for (int u=0;u<1024;++u) {
             for (int j=0;j<10;++j) {
                 f[i][u][j] += f[i-1][u][j];
                 f[i][u][j] %= mod;
                 if (x == j) {
                     // choose S[i] = x 连续
                     f[i][u][j] += f[i-1][u][j];
                     f[i][u][j] %= mod;
                 }
             }
         }
         // choose S[i] = x 不连续
         for (int v=0;v<1024;++v) {
             if (v&(1<<x)) continue;
             for (int j=0;j<10;++j) {
                 f[i][v|(1<<x)][x] += f[i-1][v][j];
                 f[i][v|(1<<x)][x] %= mod;
             }
         }
         // default
         f[i][1<<x][x]++;
     }
     long long ans = 0;
     for (int u=0;u<1024;++u) {
         for (int j=0;j<10;++j) {
             ans += f[n][u][j];
             ans %= mod;
         }
     }
     cout<<ans<<endl;
     return 0;
 }

参考

[1]. AtCoder ABC 215 E. https://atcoder.jp/contests/abc215/tasks/abc215_e

欢迎分享，引用。若转载，请联系我，谢谢配合。
本文地址：https://qoogle.top/xiaoxu-tutorial-bas-bitdp-chain-contestant/