atcoder abc215E

本文主要是介绍atcoder abc215E，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

https://atcoder.jp/contests/abc215/tasks/abc215_e

题意：

求连续相同的子序列个数，比如aaabbb算一种

思路：

考虑题目中一共只有10中字符，可以通过状压dp求解，状态表示为：dp[i][j][k],表示前i个字母中选取状态为k，并且结尾使j的所有子序列的个数，显然这样可以不重不漏表示所有的情况，
考虑转移，到第i个字符c时，一共有两种选择方式，1.要么加上当前字符串，2.或者不加当前字符，添加字符c时又有两种情况，一种是上一层就是字符c，另一种是上一层是其它字符串；
1.(1).dp[i][k][j]=dp[i-1][k][j]*2 (c=k)
1.(2).dp[i][k][j|1<<k]+=dp[i-1][k][j] (c!=k and j>>c&1=0)
2.dp[i][k][j]=dp[i-1][k][j] (c!=k)
同时每个状态也要保证合法，当枚举到字符k结尾时，要确保j>>k&1，即当前选择了k

题解：

#include <bits/stdc++.h>
#define eb emplace_back
#define divUp(a,b) (a+b-1)/b
#define mkp(x,y) make_pair(x,y)
#define all(v) begin(v),end(v)
#define int long long
#define deb(x) cout<<#x<<" "<<x<<endl;
using namespace std;
typedef unsigned long long ull;
typedef pair<int, int> pii;
bool checkP2(int n) {return n > 0 and (n & (n - 1)) == 0;};
template<typename... T>
void read(T&... args) {
    ((cin >> args), ...);
}
template<typename... T>
void put(T... args) {
    ((cout << args), ...);
}
const int N = 1 << 10, mod = 998244353;
int dp[N][11][N];
void solve() {
    int n;
    string s;
    read(n, s);
    for (int i = 1; i <= n; i++) {
        int c = s[i - 1] - 'A';
        for (int j = 0; j < 1 << 10; j++) {
            for (int k = 0; k < 10; k++) {
                if ((j >> k) & 1) {
                    dp[i][k][j] = dp[i - 1][k][j] % mod;
                    if (k == c) {
                        dp[i][k][j] = (dp[i - 1][k][j] * 2) % mod;

                    }
                }
            }
        }
        for (int j = 0; j < 1 << 10; j++) {
            if (j >> c & 1) continue;
            for (int k = 0; k < 10; k++) {
                if ((j >> k) & 1) {
                    dp[i][c][j | (1 << c)] += dp[i - 1][k][j];
                    dp[i][c][j | (1 << c)] %= mod;
                }
            }
        }
        dp[i][c][1 << c]++;
        dp[i][c][1 << c] %= mod;
    }
    int res = 0;
    for (int i = 0; i < 1 << 10; i++) {
        for (int j = 0; j < 10; j++) {
            if ((i >> j) & 1) {
                res += dp[n][j][i];
                res %= mod;
            }
        }
    }
    put(res % mod, '\n');
}
//dp[i][k][j]=dp[i-1][k][j]+...
signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
    // int _; cin >> _; while (_--)
    solve();
    return 0;
}

这篇关于atcoder abc215E的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！