Dancepted

Dancing Acceped!

Codeforces1238E. Keyboard Purchase(状压dp + 计算贡献)

题目链接:传送门


 

思路:

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

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

考虑不保存字母集合中各字母的顺序。那么问题来了,新加入一个字母后,要如何计算这个新的字母对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中各个字母的顺序,无法得知。

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

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


 

代码:O(m2m)

#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 = 0; T fg = 1; char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') fg = -1;
        ch = getchar();
    }
    while (isdigit(ch)) x = x*10+ch-'0', 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 = 1; i < n; i++) {
        int l = s[i-1] - 'a', r = s[i] - 'a';
        cnt[mk(l) | mk(r)]++;
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < mk(m); j++) {
            if (j & mk(i))
                cnt[j] += cnt[j ^ mk(i)];
        }
    }
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for (int i = 0; i < mk(m); i++) {
        for (int j = 0; j < m; j++) {
            if ((i & mk(j)) == 0) {
                int add = n-1;
                add -= cnt[i ^ mk(j)] + cnt[mk(m)-1 - (i ^ mk(j))];
                f[i ^ mk(j)] = min(f[i ^ mk(j)], f[i] + add);
            }
        }
    }
    cout << f[mk(m)-1] << endl;
    return 0;
}
View Code

 

posted on 2019-10-11 08:27 Danceped 阅读(...) 评论(...) 编辑 收藏

导航

统计