【题解】「BalticOI 2022 Day2」Boarding Passes

7KByte · 2022-06-19 08:24:10 · 题解

这题题意有点不清楚。就是我们需要在所有人开始上船之前就确定小组顺序和每个人的方向。而不是在知道小组中每个人的顺序后再决策。

观察到 g 很小，考虑直接状压。同时我们可以用调整法简单证明，对于一个小组的人，肯定存在分割点，左边的人从左边上，右边的人从右边上。

那么我们就需要快速计算贡献，如果组 x 在组 y 前面，产生的贡献是二元组 (i,j) 数量满足 i < j 且 s_i=x,s_j = y，注意如果 j 选择从右边上则相反。

我们直接跑个前缀和 f_{x,y,i} 表示组 x 在组 y 前面，y 的前 i 个数选择从左边上的贡献。对右边同理。

对于组内贡献，依然按上面的定义，只不过贡献变成 \frac{f_{x,y,i}}{2}。

状压 DP，然后转移的时候枚举分割点。由于 f 函数是个凸包，所以可以二分答案求出最优分割点。时间复杂度 \mathcal{O}(m^2n + 2^mm^2\log n)。

#define N 100005
int n, a[15][N], sz[N], m = 14, s = (1 << 15) - 1; LL f[N], u[15][15][N], v[15][15][N], c[15][N];
char ch[N];
LL calc(int w,int p,int x){
    LL sum = 0;
    rep(i, 0, m)if(1 & (w >> i))sum += u[p][i][x] * 2;
    return sum + u[p][p][x];
}
LL value(int w,int p,int x){
    LL sum = 0;
    rep(i, 0, m)if(1 & (w >> i))sum += v[p][i][x] * 2;
    return sum + v[p][p][x];
}
LL g(int w,int p,int x){
    return calc(w, p, x) + value(w, p, x + 1);
}
int main() {
    scanf("%s", ch + 1);
    n = strlen(ch + 1);
    rp(i, n){
        int op = ch[i] - 'A';
        c[op][i]++, a[op][++sz[op]] = i;
        rep(j, 0, m)c[j][i] += c[j][i - 1];
    }
    rep(x, 0, m)rep(y, 0, m){
        rp(i, n){
            u[x][y][i] = u[x][y][i - 1];
            if(ch[i] - 'A' == x)u[x][y][i] += c[y][i - 1];
        }
        pr(i, n){
            v[x][y][i] = v[x][y][i + 1];
            if(ch[i] - 'A' == x)v[x][y][i] += c[y][n] - c[y][i];
        }
    }
    memset(f, 0x3f, sizeof(f));
    f[0] = 0;
    rep(i, 0, s - 1)rep(j, 0, m)if(! (1 & (i >> j))){
        int t = i | (1 << j);
        int l = 0, r = sz[j] - 1, ed = sz[j];
        while(l <= r){
            int mid = (l + r) >> 1;
            if(g(i, j, a[j][mid]) < g(i, j, a[j][mid + 1]))ed = mid, r = mid - 1;
            else l = mid + 1;
        }
        cmn(f[t], f[i] + g(i, j, a[j][ed]));
    }
    cout << f[s] / 2;
    if(f[s] & 1)pc('.'), pc('5');
    return 0;
}