CF917C Pollywog

· · 题解

F. CF917C Pollywog *2900

注意到 x 和 k 很小而 n 很大，同时所有青蛙之间的距离必然不超过 k（因为每次只能跳最左边的青蛙），以及这 q 个奇奇怪怪的限制（联想到 “美食家” 这题），矩阵快速幂没得跑了。

预处理转移矩阵 A 的幂，在断点处特殊考虑，每次矩阵快速幂时只需向量乘矩阵，时间复杂度为 \mathcal{O}((q + |A|)|A| ^ 2\log n)（这里 |A| 表示 A 的规模而不是行列式啊喂）。

这题唯一有技术含量的地方在于状态的设计。

我们有两条路，一是设 f_{i, j} 表示最左边的青蛙在 i 处，剩下来的青蛙状态为 j 时最小体力花费。这样由于每次跳动最多会让 i 增加 k - x + 1，所以共需要记录 (k - x + 1)\dbinom {k - 1} {x - 1} 个状态，算一下当 x = 4，k = 8 时共有 170 个状态，即 |A| = 170，勉强可以通过。

另一种是设 f_{i, j} 表示当前的 视野 在 i\sim i + k - 1 处，以这样的视野观察到青蛙的状态为 j 时的最小体力花费。具体地，j 的第 p 位为 1 当且仅当 i + p 处有青蛙。这样一来，若 2\mid j 即 i 处没有青蛙时，转移到 i + 1 只需给 j 除以 2 而非跳最左边的青蛙。因此只需记录 \dbinom k x 个状态，当 x = 4，k = 8 时只有 70 个状态，稳稳通过。

所以说有的时候巧妙的状态设计是很重要的。

#include <bits/stdc++.h>
using namespace std;
const int N = 70 + 5;
void cmin(long long &x, long long y) {x = x < y ? x : y;}
map <int, int> mp;
int x, k, n, q, sz, c[N], lab[1 << 8], msk[N];
struct mat {
    long long a[N][N];
    mat() {memset(a, 0x3f, sizeof(a));}
    mat operator * (mat x) {
        mat y;
        for(int i = 1; i <= sz; i++)
            for(int j = 1; j <= sz; j++)
                for(int k = 1; k <= sz; k++)
                    cmin(y.a[i][k], a[i][j] + x.a[j][k]);
        return y;
    }
    mat operator / (mat x) {
        mat y;
        for(int i = 1; i <= sz; i++)
            for(int j = 1; j <= sz; j++)
                cmin(y.a[1][j], a[1][i] + x.a[i][j]);
        return y;
    }
} tr, pw[27], I;
struct stone {
    int p, w;
    bool operator < (const stone &v) const {return p < v.p;}
} s[N];
int main() {
    // freopen("1.in", "r", stdin);
    cin >> x >> k >> n >> q;
    for(int i = 0; i < 1 << k; i++) if(__builtin_popcount(i) == x) msk[lab[i] = ++sz] = i;
    for(int i = 1; i <= k; i++) cin >> c[i];
    for(int i = 0; i < 1 << k; i++) {
        if(!lab[i]) continue;
        if(i & 1 ^ 1) {tr.a[lab[i]][lab[i >> 1]] = 0; continue;}
        for(int p = 1; p <= k; p++) {
            if(i >> p & 1) continue;
            tr.a[lab[i]][lab[(i | 1 << p) >> 1]] = c[p];
        }
    }
    pw[0] = tr;
    for(int i = 1; 1 << i < n; i++) pw[i] = pw[i - 1] * pw[i - 1];
    for(int i = 1; i <= q; i++) cin >> s[i].p >> s[i].w, mp[s[i].p] = s[i].w;
    sort(s + 1, s + q + 1);
    if(s[q].p < n) s[++q] = {n};
    I.a[1][1] = 0;
    for(int i = 1, cur = 1; i <= q; i++) {
        int to = min(n - x + 1, s[i].p);
        for(int j = 26; ~j; j--) {
            if(cur + (1 << j) > to - k) continue;
            cur += 1 << j, I = I / pw[j];
        }
        while(cur < to) {
            mat nxt;
            memset(nxt.a, 0x3f, sizeof(nxt.a));
            for(int i = 1; i <= sz; i++) {
                int S = msk[i];
                if(S & 1 ^ 1) {cmin(nxt.a[1][lab[S >> 1]], I.a[1][i]); continue;}
                for(int p = 1; p <= k; p++) {
                    if(S >> p & 1) continue;
                    long long nv = I.a[1][i] + c[p] + (mp.find(cur + p) == mp.end() ? 0 : mp[cur + p]);
                    cmin(nxt.a[1][lab[(S | 1 << p) >> 1]], nv);
                }
            }
            cur++, I = nxt;
        }
    }
    cout << I.a[1][1] << endl;
    return 0;
}

/*
2022/4/28
start thinking at ??:??

这题我做过.jpg.

start coding at 20:40
finish debugging at 21:10
*/