Codeforces1238E. Keyboard Purchase（状压dp + 计算贡献）

题目链接：传送门

思路：

题目中的m为20，而不是26，显然在疯狂暗示要用状压来做。

考虑状压字母集合。如果想要保存字母集合中的各字母的顺序，那就和经典的n！的状态的状压没什么区别了，时间复杂度为O(m²2^m)，是不可行的，所以本题肯定有更好的做法。

考虑不保存字母集合中各字母的顺序。那么问题来了，新加入一个字母后，要如何计算这个新的字母对slowness产生的影响呢？

不妨设当前已经被选过的字母集合为i(0 ≤ i ≤ (1<<m))，当前要加入的字母j(0 ≤ j < m)，且(i>>j&1) == 0。

考虑每次都把新的字母j放在i中的所有字母的右边，则字母j的加入对答案的影响为：

$\sum_{k\in i}cnt_{j,k}*(pos_{j}-pos_{k}) +\sum_{k\notin i}cnt_{j,k}*(pos_{k}-pos_{j}) $，其中$cnt_{j, k}$表示输入密码时，从j移动到k和从k移动到j的次数之和

其中，$pos_{j}$已知，为i中1的个数，但是pos_{k}因为没有记录i中各个字母的顺序，无法得知。

那么我们不妨只直接计算字母j对应的$pos_{j}$对答案产生的影响：$\sum_{k\in i}cnt_{j,k}*pos_{j}-\sum_{k\notin i}cnt_{j,k}*pos_{j}$

这样的做法还是O(m²2^m)，但是预处理出这个东西$\sum_{k\in i}cnt_{j,k}*pos_{j}$，就可以把时间复杂度优化到O(m2^m)了。

代码：O(m2^m)

#include <bits/stdc++.h>

#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

#define N 100005

#define M 20

#define INF 0x3f3f3f3f

#define mk(x) (1<<x) // be conscious if mask x exceeds int

#define sz(x) ((int)x.size())

#define mp(a,b) make_pair(a, b)

#define endl '\n'

#define lowbit(x) (x&-x)

using namespace std;

typedef long long ll;

typedef double db;

/** fast read **/

template <typename T>

inline void read(T &x) {

    x = ; T fg = ; char ch = getchar();

    while (!isdigit(ch)) {

        if (ch == '-') fg = -;

        ch = getchar();

    }

    while (isdigit(ch)) x = x*+ch-'', ch = getchar();

    x = fg * x;

}

template <typename T, typename... Args>

inline void read(T &x, Args &... args) { read(x), read(args...); }

string s;

int f[mk(M)], cnt[mk(M)];

int main()

{

    int n, m; read(n, m);

    cin >> s;

    for (int i = ; i < n; i++) {

        int l = s[i-] - 'a', r = s[i] - 'a';

        cnt[mk(l) | mk(r)]++;

    }

    for (int i = ; i < m; i++) {

        for (int j = ; j < mk(m); j++) {

            if (j & mk(i))

                cnt[j] += cnt[j ^ mk(i)];

        }

    }

    memset(f, 0x3f, sizeof f);

    f[] = ;

    for (int i = ; i < mk(m); i++) {

        for (int j = ; j < m; j++) {

            if ((i & mk(j)) == ) {

                int add = n-;

                add -= cnt[i ^ mk(j)] + cnt[mk(m)- - (i ^ mk(j))];

                f[i ^ mk(j)] = min(f[i ^ mk(j)], f[i] + add);

            }

        }

    }

    cout << f[mk(m)-] << endl;

    return ;

}

巴特西

Codeforces1238E. Keyboard Purchase（状压dp + 计算贡献）

最新文章

热门文章